Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics
http://hdl.handle.net/2429/29986
Wed, 27 May 2015 06:31:45 GMT2015-05-27T06:31:45ZA Numerical Quantum and Classical Adversary (Issued:2010-07-25)
http://hdl.handle.net/2429/30937
The Quantum Adversary Method has proven to be a successful technique for deriving lower bounds on a wide variety of problems. However, it assumes perfect quantum computation, which in most modern devices, is unrealistic. Here, we develop a generalization of this technique without this assumption, which can be applied to arbitrary small problems automatically. To do this, we start by reformulating the objective value of the semidefinite program of the spectral adversary method. By relating the final measurement stage of a quantum computation to remote state preparation, we prove that the optimal value of the new objective corresponds to the probability that the quantum computer will output the correct value after a specified number of queries. Once in this framework, the addition of decoherence is natural. In particular, the optimum probability of success can be determined for any probability of phase error. In the limit of complete phase decoherence, we recover the optimal p! robability of success for a classical computation. Our semidefinite programming formulation is suitably general, and so has application outside that of algorithms. In particular, we apply it to the optimization of quantum clocks.
Sun, 25 Jul 2010 00:00:00 GMThttp://hdl.handle.net/2429/309372010-07-25T00:00:00ZUnifying Classical Spin Models Using A Quantum Formalism (Issued:2010-07-23)
http://hdl.handle.net/2429/30936
We have recently shown that the partition function of any classical spin model, including all discrete standard statistical models and all Abelian discrete lattice gauge theories, can be expressed as the specific instance of the partition function of a four dimensional Ising lattice gauge theory. This unifies models with apparently very different features (global vs. local symmetries, many body interactions, different dimensions, etc) in a single complete model. The proof of the result uses techniques from quantum information. In this talk we review these mappings and discuss recent developments, including quantum algorithms to approximate the partition function.
Fri, 23 Jul 2010 00:00:00 GMThttp://hdl.handle.net/2429/309362010-07-23T00:00:00ZCorrelations in Measurement-Based Quantum Computing and Bell Inequalities (Issued:2010-07-24)
http://hdl.handle.net/2429/30935
Measurement-based quantum computation (or the one-way quantum computation) is a model in which a series of adaptive single qubit measurements upon an entangled resource state can produce classical output data equivalent to an arbitrary quantum logic circuit. Loosely speaking, the correlations in these measurements can be considered the resource which allows the computation to be performed.
Bell inequalities demonstrate that quantum mechanics permits the outcomes of sets of measurements to be correlated in ways incompatible with the predictions of any local hidden variable theory, including classical physics. In the Bell inequality, and multi-party generalisations, a set of single-qubit measurements are performed, on spatially separated systems. Correlations in these measurements can act as a signature that no local hidden variable description of the experiment is possible.
At first sight, we see superficial similarities between these settings. In both cases, non-classical correlations play a central role. However, there are also some key differences. Most importantly, measurement-based quantum computing requires adaptive measurements, at odds with the spatial-separated nature of Bell inequality experiments. Nevertheless some striking connections have been reported [1], [2] particularly between GHZ-type paradoxes and deterministic MBQC computations, and between CHSH-type Bell inequalities and non-deterministic MBQC correlations [1], [3]. In my talk I will survey these works and some recent results [3], [4] from my group at UCL, in which a number of connections between multi-party Bell inequalities and MBQC are explored.
[1] J. Anders and D.E. Browne, "The Computational Power of Correlations", Physical Review Letters 102, 050502 (2009)
[2] R. Raussendorf, "Quantum computation, discreteness, and contextuality", arxiv:0907.5449
[3] M. J. Hoban, E.T. Campbell, K. Loukopolous, D.E. Browne, "Non-adaptive measurement-based quantum computation and multi-party Bell inequalties", in preparation.
[4] M. J. Hoban and D.E. Browne, in preparation.
Sat, 24 Jul 2010 00:00:00 GMThttp://hdl.handle.net/2429/309352010-07-24T00:00:00ZQuantum Algorithms from Topological Quantum Field Theories (Issued:2010-07-24)
http://hdl.handle.net/2429/30934
Topological Quantum Field Theories (or TQFTs) are abstract constructions from category theory and mathematical physics. Their conception was originally motivated by the search for a physical theory that unifies general relativity and quantum mechanics. At its core, a TQFT is a map from manifolds (e.g., spacetimes) to linear maps (e.g., quantum operations) that satisfies some physically sensible properties. For instance, the disjoint union of two manifolds must be mapped to the tensor product of the two corresponding linear maps. To manifolds without boundary, a TQFT assigns a topologically invariant number called a quantum invariant. This discovery added a beautiful new direction in the study of manifold invariants in pure mathematics. For this reason and many others, this area has seen a tremendous amount of work in the past two decades, from physicists and mathematicians alike.
In this talk, we will discuss how this theory can be applied to design quantum algorithms for approximating certain quantum invariants. The aim of the talk is to give an accessible introduction to some of the ideas in this area, and to motivate quantum computation enthusiasts to study it further. We will begin with the simplest two-dimensional state-sum models. These examples are quite attractive, since they can be described in a combinatorial manner by means of triangulations. We will then define a three-dimensional state-sum TQFT, called the Turaev-Viro theory. Finally, we will discuss a recent result (joint with Stephen Jordan, Robert Koenig, and Ben Reichardt) showing that approximating the Turaev-Viro quantum invariant is a universal problem for quantum computation.
Sat, 24 Jul 2010 00:00:00 GMThttp://hdl.handle.net/2429/309342010-07-24T00:00:00Z