Much research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians with Hamming symmetric potentials, such as the well studied "spike" example. Due to the large amount of symmetry in these potentials such problems are readily open to analysis both analytically and computationally. However, more realistic potentials do not have such a high degree of symmetry and may have many local minima. Here we present a somewhat more realistic class of problems consisting of many individually Hamming symmetric potential wells. For two or three such wells we demonstrate that such a problem can be solved exactly in time polynomial in the number of qubits and wells. For greater than three wells, we present a tight binding approach with which to efficiently analyze the performance of such Hamiltonians in an adiabatic computation. We provide several basic examples designed to highlight the usefulness of this toy model and to give insight into using the tight binding approach to examining it, including: (1) adiabatic unstructured search with a transverse field driver and a prior guess to the marked item and (2) a scheme for adiabatically simulating the ground states of small collections of strongly interacting spins, with an explicit demonstration for an Ising model Hamiltonian.

UR - https://arxiv.org/abs/1905.07461 ER - TY - JOUR T1 - Quantum Algorithm for Simulating the Wave Equation JF - Phys. Rev. A Y1 - 2019 A1 - Pedro C.S. Costa A1 - Stephen P. Jordan A1 - Aaron Ostrander AB -We present a quantum algorithm for simulating the wave equation under Dirichlet and Neumann boundary conditions. The algorithm uses Hamiltonian simulation and quantum linear system algorithms as subroutines. It relies on factorizations of discretized Laplacian operators to allow for improved scaling in truncation errors and improved scaling for state preparation relative to general purpose linear differential equation algorithms. We also consider using Hamiltonian simulation for Klein-Gordon equations and Maxwell's equations.

VL - 99 UR - https://arxiv.org/abs/1711.05394 CP - 012323 U5 - https://doi.org/10.1103/PhysRevA.99.012323 ER - TY - JOUR T1 - BQP-completeness of Scattering in Scalar Quantum Field Theory JF - Quantum Y1 - 2018 A1 - Stephen P. Jordan A1 - Hari Krovi A1 - Keith S. M. Lee A1 - John Preskill AB -Recent work has shown that quantum computers can compute scattering probabilities in massive quantum field theories, with a run time that is polynomial in the number of particles, their energy, and the desired precision. Here we study a closely related quantum field-theoretical problem: estimating the vacuum-to-vacuum transition amplitude, in the presence of spacetime-dependent classical sources, for a massive scalar field theory in (1+1) dimensions. We show that this problem is BQP-hard; in other words, its solution enables one to solve any problem that is solvable in polynomial time by a quantum computer. Hence, the vacuum-to-vacuum amplitude cannot be accurately estimated by any efficient classical algorithm, even if the field theory is very weakly coupled, unless BQP=BPP. Furthermore, the corresponding decision problem can be solved by a quantum computer in a time scaling polynomially with the number of bits needed to specify the classical source fields, and this problem is therefore BQP-complete. Our construction can be regarded as an idealized architecture for a universal quantum computer in a laboratory system described by massive phi^4 theory coupled to classical spacetime-dependent sources.

VL - 2 U4 - 44 UR - https://quantum-journal.org/papers/q-2018-01-08-44/ U5 - 10.22331/q-2018-01-08-44 ER - TY - JOUR T1 - Diffusion Monte Carlo Versus Adiabatic Computation for Local Hamiltonians JF - Physical Review A Y1 - 2018 A1 - Jacob Bringewatt A1 - William Dorland A1 - Stephen P. Jordan A1 - Alan Mink AB -Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real, nonnegative amplitudes. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-k-SAT problems, use k-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved n-body interactions. Here we present a new 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.

VL - 97 U4 - 022323 UR - https://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.022323 CP - 2 U5 - 10.1103/PhysRevA.97.022323 ER - TY - JOUR T1 - Quantum Cryptanalysis: Shor, Grover, and Beyond JF - IEEE Security & Privacy Y1 - 2018 A1 - Stephen P. Jordan A1 - Yi-Kai Liu VL - 16 U4 - 14-21 CP - 5 U5 - 10.1109/MSP.2018.3761719 ER - TY - JOUR T1 - Experimentally Generated Random Numbers Certified by the Impossibility of Superluminal Signaling Y1 - 2017 A1 - Peter Bierhorst A1 - Emanuel Knill A1 - Scott Glancy A1 - Alan Mink A1 - Stephen P. Jordan A1 - Andrea Rommal A1 - Yi-Kai Liu A1 - Bradley Christensen A1 - Sae Woo Nam A1 - Lynden K. Shalm AB -Random numbers are an important resource for applications such as numerical simulation and secure communication. However, it is difficult to certify whether a physical random number generator is truly unpredictable. Here, we exploit the phenomenon of quantum nonlocality in a loophole-free photonic Bell test experiment for the generation of randomness that cannot be predicted within any physical theory that allows one to make independent measurement choices and prohibits superluminal signaling. To certify and quantify the randomness, we describe a new protocol that performs well in an experimental regime characterized by low violation of Bell inequalities. Applying an extractor function to our data, we obtained 256 new random bits, uniform to within 0.001.

UR - https://arxiv.org/abs/1702.05178# ER - TY - JOUR T1 - Fast optimization algorithms and the cosmological constant JF - Physical Review D Y1 - 2017 A1 - Ning Bao A1 - Raphael Bousso A1 - Stephen P. Jordan A1 - Brad Lackey AB -Denef and Douglas have observed that in certain landscape models the problem of finding small values of the cosmological constant is a large instance of an NP-hard problem. The number of elementary operations (quantum gates) needed to solve this problem by brute force search exceeds the estimated computational capacity of the observable universe. Here we describe a way out of this puzzling circumstance: despite being NP-hard, the problem of finding a small cosmological constant can be attacked by more sophisticated algorithms whose performance vastly exceeds brute force search. In fact, in some parameter regimes the average-case complexity is polynomial. We demonstrate this by explicitly finding a cosmological constant of order 10−120 in a randomly generated 109 -dimensional ADK landscape.

VL - 96 U4 - 103512 UR - https://arxiv.org/abs/1706.08503 CP - 10 U5 - 10.1103/PhysRevD.96.103512 ER - TY - JOUR T1 - Fast quantum computation at arbitrarily low energy JF - Physical Review A Y1 - 2017 A1 - Stephen P. Jordan AB -One version of the energy-time uncertainty principle states that the minimum time T⊥ for a quantum system to evolve from a given state to any orthogonal state is h/(4ΔE), where ΔE is the energy uncertainty. A related bound called the Margolus-Levitin theorem states that T⊥≥h/(2⟨E⟩), where ⟨E⟩ is the expectation value of energy and the ground energy is taken to be zero. Many subsequent works have interpreted T⊥ as defining a minimal time for an elementary computational operation and correspondingly a fundamental limit on clock speed determined by a system's energy. Here we present local time-independent Hamiltonians in which computational clock speed becomes arbitrarily large relative to ⟨E⟩ and ΔE as the number of computational steps goes to infinity. We argue that energy considerations alone are not sufficient to obtain an upper bound on computational speed, and that additional physical assumptions such as limits to information density and information transmission speed are necessary to obtain such a bound.

VL - 95 U4 - 032305 UR - http://link.aps.org/doi/10.1103/PhysRevA.95.032305 U5 - 10.1103/PhysRevA.95.032305 ER - TY - JOUR T1 - Modulus of continuity eigenvalue bounds for homogeneous graphs and convex subgraphs with applications to quantum Hamiltonians JF - Journal of Mathematical Analysis and Applications Y1 - 2017 A1 - Michael Jarret A1 - Stephen P. Jordan AB -We adapt modulus of continuity estimates to the study of spectra of combinatorial graph Laplacians, as well as the Dirichlet spectra of certain weighted Laplacians. The latter case is equivalent to stoquastic Hamiltonians and is of current interest in both condensed matter physics and quantum computing. In particular, we introduce a new technique which bounds the spectral gap of such Laplacians (Hamiltonians) by studying the limiting behavior of the oscillations of their eigenvectors when introduced into the heat equation. Our approach is based on recent advances in the PDE literature, which include a proof of the fundamental gap theorem by Andrews and Clutterbuck.

VL - 452 U4 - 1269-1290 UR - http://www.sciencedirect.com/science/article/pii/S0022247X1730272X CP - 2 U5 - 10.1016/j.jmaa.2017.03.030 ER - TY - JOUR T1 - Adiabatic optimization versus diffusion Monte Carlo JF - Physical Review A Y1 - 2016 A1 - Michael Jarret A1 - Stephen P. Jordan A1 - Brad Lackey AB -Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here, we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between L1 and L2 normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-k-SAT at k=2,3,4.

VL - 94 U4 - 042318 UR - https://arxiv.org/abs/1607.03389 ER - TY - JOUR T1 - Black Holes, Quantum Mechanics, and the Limits of Polynomial-time Computability JF - XRDS Y1 - 2016 A1 - Stephen P. Jordan AB -Which computational problems can be solved in polynomial-time and which cannot? Though seemingly technical, this question has wide-ranging implications and brings us to the heart of both theoretical computer science and modern physics.

VL - 23 U4 - 30–33 UR - http://doi.acm.org/10.1145/2983539 U5 - 10.1145/2983539 ER - TY - JOUR T1 - Grover search and the no-signaling principle JF - Physical Review Letters Y1 - 2016 A1 - Ning Bao A1 - Adam Bouland A1 - Stephen P. Jordan AB -From an information processing point of view, two of the key properties of quantum physics are the no-signaling principle and the Grover search lower bound. That is, despite admitting stronger-than-classical correlations, quantum mechanics does not imply superluminal signaling, and despite a form of exponential parallelism, quantum mechanics does not imply polynomial-time brute force solution of NP-complete problems. Here, we investigate the degree to which these two properties are connected. We examine four classes of deviations from quantum mechanics, for which we draw inspiration from the literature on the black hole information paradox: nonunitary dynamics, non-Born-rule measurement, cloning, and postselection. We find that each model admits superluminal signaling if and only if it admits a query complexity speedup over Grover's algorithm. Furthermore, we show that the physical resources required to send a superluminal signal scale polynomially with the resources needed to speed up Grover's algorithm. Hence, one can perform a physically reasonable experiment demonstrating superluminal signaling if and only if one can perform a reasonable experiment inducing a speedup over Grover's algorithm.

VL - 117 U4 - 120501 UR - http://arxiv.org/abs/1511.00657 ER - TY - JOUR T1 - Yang-Baxter operators need quantum entanglement to distinguish knots JF - Journal of Physics A Y1 - 2016 A1 - Gorjan Alagic A1 - Michael Jarret A1 - Stephen P. Jordan AB - Any solution to the Yang-Baxter equation yields a family of representations of braid groups. Under certain conditions, identified by Turaev, the appropriately normalized trace of these representations yields a link invariant. Any Yang-Baxter solution can be interpreted as a two-qudit quantum gate. Here we show that if this gate is non-entangling, then the resulting invariant of knots is trivial. We thus obtain a general connection between topological entanglement and quantum entanglement, as suggested by Kauffman et al. VL - 49 U4 - 075203 UR - http://arxiv.org/abs/1507.05979 CP - 7 U5 - 10.1088/1751-8113/49/7/075203 ER - TY - JOUR T1 - Adiabatic optimization without local minima JF - Quantum Information and Computation Y1 - 2015 A1 - Michael Jarret A1 - Stephen P. Jordan AB - Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we investigate the even more basic question of whether adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there are no local energy minima other than the global minimum. Surprisingly, we find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. In this counterexample, the ground state wavefunction consists of two "lobes" separated by a region of exponentially small amplitude. Conversely, we prove if the ground state wavefunction is single-peaked then the eigenvalue gap scales at worst as one over the square of the number of vertices. VL - 15 U4 - 181-199 UR - http://arxiv.org/abs/1405.7552 CP - 3-4 J1 - Quantum Information and Computation ER - TY - JOUR T1 - Classical simulation of Yang-Baxter gates JF - 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) Y1 - 2014 A1 - Gorjan Alagic A1 - Aniruddha Bapat A1 - Stephen P. Jordan AB - A unitary operator that satisfies the constant Yang-Baxter equation immediately yields a unitary representation of the braid group B n for every $n \ge 2$. If we view such an operator as a quantum-computational gate, then topological braiding corresponds to a quantum circuit. A basic question is when such a representation affords universal quantum computation. In this work, we show how to classically simulate these circuits when the gate in question belongs to certain families of solutions to the Yang-Baxter equation. These include all of the qubit (i.e., $d = 2$) solutions, and some simple families that include solutions for arbitrary $d \ge 2$. Our main tool is a probabilistic classical algorithm for efficient simulation of a more general class of quantum circuits. This algorithm may be of use outside the present setting. VL - 27 U4 - 161-175 UR - http://arxiv.org/abs/1407.1361v1 J1 - 9th Conference on the Theory of Quantum Computation U5 - 10.4230/LIPIcs.TQC.2014.161 ER - TY - JOUR T1 - The Fundamental Gap for a Class of Schrödinger Operators on Path and Hypercube Graphs JF - Journal of Mathematical Physics Y1 - 2014 A1 - Michael Jarret A1 - Stephen P. Jordan AB - We consider the difference between the two lowest eigenvalues (the fundamental gap) of a Schr\"{o}dinger operator acting on a class of graphs. In particular, we derive tight bounds for the gap of Schr\"{o}dinger operators with convex potentials acting on the path graph. Additionally, for the hypercube graph, we derive a tight bound for the gap of Schr\"{o}dinger operators with convex potentials dependent only upon vertex Hamming weight. Our proof makes use of tools from the literature of the fundamental gap theorem as proved in the continuum combined with techniques unique to the discrete case. We prove the tight bound for the hypercube graph as a corollary to our path graph results. VL - 55 U4 - 052104 UR - http://arxiv.org/abs/1403.1473v1 CP - 5 J1 - J. Math. Phys. U5 - 10.1063/1.4878120 ER - TY - Generic T1 - Partial-indistinguishability obfuscation using braids T2 - In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC14) Y1 - 2014 A1 - Gorjan Alagic A1 - Stacey Jeffery A1 - Stephen P. Jordan AB -An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mainly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.

JA - In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC14) UR - http://arxiv.org/abs/1212.6358 ER - TY - JOUR T1 - Quantum Algorithms for Fermionic Quantum Field Theories Y1 - 2014 A1 - Stephen P. Jordan A1 - Keith S. M. Lee A1 - John Preskill AB - Extending previous work on scalar field theories, we develop a quantum algorithm to compute relativistic scattering amplitudes in fermionic field theories, exemplified by the massive Gross-Neveu model, a theory in two spacetime dimensions with quartic interactions. The algorithm introduces new techniques to meet the additional challenges posed by the characteristics of fermionic fields, and its run time is polynomial in the desired precision and the energy. Thus, it constitutes further progress towards an efficient quantum algorithm for simulating the Standard Model of particle physics. UR - http://arxiv.org/abs/1404.7115v1 ER - TY - JOUR T1 - Quantum Computation of Scattering in Scalar Quantum Field Theories JF - Quantum Information and Computation Y1 - 2014 A1 - Stephen P. Jordan A1 - Keith S. M. Lee A1 - John Preskill AB - Quantum field theory provides the framework for the most fundamental physical theories to be confirmed experimentally, and has enabled predictions of unprecedented precision. However, calculations of physical observables often require great computational complexity and can generally be performed only when the interaction strength is weak. A full understanding of the foundations and rich consequences of quantum field theory remains an outstanding challenge. We develop a quantum algorithm to compute relativistic scattering amplitudes in massive phi-fourth theory in spacetime of four and fewer dimensions. The algorithm runs in a time that is polynomial in the number of particles, their energy, and the desired precision, and applies at both weak and strong coupling. Thus, it offers exponential speedup over existing classical methods at high precision or strong coupling. VL - 14 U4 - 1014-1080 UR - http://arxiv.org/abs/1112.4833v1 CP - 11-12 J1 - Quantum Information and Computation 14 ER - TY - JOUR T1 - Strong Equivalence of Reversible Circuits is coNP-complete JF - Quantum Information Computation Y1 - 2014 A1 - Stephen P. Jordan KW - complexity KW - reversible circuits AB -It is well-known that deciding equivalence of logic circuits is a coNP-complete problem. As a corollary, the problem of deciding weak equivalence of reversible circuits, i.e. allowing initialized ancilla bits in the input and ignoring "garbage" ancilla bits in the output, is also coNP-complete. The complexity of deciding strong equivalence, including the ancilla bits, is less obvious and may depend on gate set. Here we use Barrington's theorem to show that deciding strong equivalence of reversible circuits built from the Fredkin gate is coNP-complete. This implies coNP-completeness of deciding strong equivalence for other commonly used universal reversible gate sets, including any gate set that includes the Toffoli or Fredkin gate.

VL - 14 U4 - 1302–1307 UR - http://dl.acm.org/citation.cfm?id=2685179.2685182 ER - TY - JOUR T1 - Testing quantum expanders is co-QMA-complete JF - Physical Review A Y1 - 2013 A1 - Adam D. Bookatz A1 - Stephen P. Jordan A1 - Yi-Kai Liu A1 - Pawel Wocjan AB - A quantum expander is a unital quantum channel that is rapidly mixing, has only a few Kraus operators, and can be implemented efficiently on a quantum computer. We consider the problem of estimating the mixing time (i.e., the spectral gap) of a quantum expander. We show that this problem is co-QMA-complete. This has applications to testing randomized constructions of quantum expanders, and studying thermalization of open quantum systems. VL - 87 UR - http://arxiv.org/abs/1210.0787v2 CP - 4 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.87.042317 ER - TY - JOUR T1 - Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems JF - Quantum Information and Computation Y1 - 2012 A1 - Stephen P. Jordan A1 - Hirotada Kobayashi A1 - Daniel Nagaj A1 - Harumichi Nishimura AB - This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, QCMA = QCMA1. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, e.g., {Hadamard, Toffoli, NOT}. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that additively adjusts the success probability, which may be of independent interest. VL - 12 U4 - 461-471 UR - http://arxiv.org/abs/1111.5306v2 CP - 5-6 J1 - Quantum Information and Computation Vol. 12 No. 5/6 pg. 461-471 (2012) ER - TY - JOUR T1 - Quantum Algorithms for Quantum Field Theories JF - Science Y1 - 2012 A1 - Stephen P. Jordan A1 - Keith S. M. Lee A1 - John Preskill AB - Quantum field theory reconciles quantum mechanics and special relativity, and plays a central role in many areas of physics. We develop a quantum algorithm to compute relativistic scattering probabilities in a massive quantum field theory with quartic self-interactions (phi-fourth theory) in spacetime of four and fewer dimensions. Its run time is polynomial in the number of particles, their energy, and the desired precision, and applies at both weak and strong coupling. In the strong-coupling and high-precision regimes, our quantum algorithm achieves exponential speedup over the fastest known classical algorithm. VL - 336 U4 - 1130 - 1133 UR - http://arxiv.org/abs/1111.3633v2 CP - 6085 J1 - Science U5 - 10.1126/science.1217069 ER - TY - Generic T1 - Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit T2 - In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC11) Y1 - 2011 A1 - Stephen P. Jordan A1 - Gorjan Alagic AB -The Turaev-Viro invariants are scalar topological invariants of three-dimensional manifolds. Here we show that the problem of estimating the Fibonacci version of the Turaev-Viro invariant of a mapping torus is a complete problem for the one clean qubit complexity class (DQC1). This complements a previous result showing that estimating the Turaev-Viro invariant for arbitrary manifolds presented as Heegaard splittings is a complete problem for the standard quantum computation model (BQP). We also discuss a beautiful analogy between these results and previously known results on the computational complexity of approximating the Jones polynomial.

JA - In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC11) UR - http://arxiv.org/abs/1105.5100 ER - TY - JOUR T1 - Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation JF - Physical Review A Y1 - 2010 A1 - Gorjan Alagic A1 - Stephen P. Jordan A1 - Robert Koenig A1 - Ben W. Reichardt AB - The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2+1)-D topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a novel relation between the task of distinguishing non-homeomorphic 3-manifolds and the power of a general quantum computer. VL - 82 UR - http://arxiv.org/abs/1003.0923v1 CP - 4 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.82.040302 ER - TY - JOUR T1 - On the degeneracy of SU(3)k topological phases Y1 - 2010 A1 - Stephen P. Jordan A1 - Toufik Mansour A1 - Simone Severini AB -The ground state degeneracy of an $SU(N)_k$ topological phase with $n$ quasiparticle excitations is relevant quantity for quantum computation, condensed matter physics, and knot theory. It is an open question to find a closed formula for this degeneracy for any $N > 2$. Here we present the problem in an explicit combinatorial way and analyze the case N=3. While not finding a complete closed-form solution, we obtain generating functions and solve some special cases.

UR - http://arxiv.org/abs/1009.0114v1 ER - TY - JOUR T1 - Permutational Quantum Computing JF - Quantum Information & Computation Y1 - 2010 A1 - Stephen P. Jordan AB -In topological quantum computation the geometric details of a particle trajectory are irrelevant; only the topology matters. Taking this one step further, we consider a model of computation that disregards even the topology of the particle trajectory, and computes by permuting particles. Whereas topological quantum computation requires anyons, permutational quantum computation can be performed with ordinary spin-1/2 particles, using a variant of the spin-network scheme of Marzuoli and Rasetti. We do not know whether permutational computation is universal. It may represent a new complexity class within BQP. Nevertheless, permutational quantum computers can in polynomial time approximate matrix elements of certain irreducible representations of the symmetric group and simulate certain processes in the Ponzano-Regge spin foam model of quantum gravity. No polynomial time classical algorithms for these problems are known.

VL - 10 U4 - 470-497 UR - http://dl.acm.org/citation.cfm?id=2011369 CP - 5 J1 - Quantum Information and Computation Vol. 10 pg. 470 (2010) ER - TY - JOUR T1 - QMA-complete problems for stoquastic Hamiltonians and Markov matrices JF - Physical Review A Y1 - 2010 A1 - Stephen P. Jordan A1 - David Gosset A1 - Peter J. Love AB - We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is QMA-complete. We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration free Hamiltonian is universal. Our results give a new QMA-complete problem arising in the classical setting of Markov chains, and new adiabatically universal Hamiltonians that arise in many physical systems. VL - 81 UR - http://arxiv.org/abs/0905.4755v2 CP - 3 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.81.032331 ER - TY - JOUR T1 - Discrete-query quantum algorithm for NAND trees JF - Theory of Computing Y1 - 2009 A1 - Andrew M. Childs A1 - Richard Cleve A1 - Stephen P. Jordan A1 - David Yeung AB - Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0. VL - 5 U4 - 119 - 123 UR - http://arxiv.org/abs/quant-ph/0702160v1 CP - 1 J1 - Theory of Comput. U5 - 10.4086/toc.2009.v005a005 ER - TY - JOUR T1 - Efficient quantum circuits for arbitrary sparse unitaries JF - Physical Review A Y1 - 2009 A1 - Stephen P. Jordan A1 - Pawel Wocjan AB - Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms. VL - 80 UR - http://arxiv.org/abs/0904.2211v2 CP - 6 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.80.062301 ER - TY - JOUR T1 - Efficient quantum processing of ideals in finite rings Y1 - 2009 A1 - Pawel M. Wocjan A1 - Stephen P. Jordan A1 - Hamed Ahmadi A1 - Joseph P. Brennan AB - Suppose we are given black-box access to a finite ring R, and a list of generators for an ideal I in R. We show how to find an additive basis representation for I in poly(log |R|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for R itself. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings. In particular we show how to test whether two ideals are identical, find their intersection, find their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit, and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. These problems appear to be hard classically. UR - http://arxiv.org/abs/0908.0022v1 ER - TY - JOUR T1 - Estimating Jones and HOMFLY polynomials with One Clean Qubit JF - Quantum Information and Computation Y1 - 2009 A1 - Stephen P. Jordan A1 - Pawel Wocjan AB -The Jones and HOMFLY polynomials are link invariants with close connections to quantum computing. It was recently shown that finding a certain approximation to the Jones polynomial of the trace closure of a braid at the fifth root of unity is a complete problem for the one clean qubit complexity class. This is the class of problems solvable in polynomial time on a quantum computer acting on an initial state in which one qubit is pure and the rest are maximally mixed. Here we generalize this result by showing that one clean qubit computers can efficiently approximate the Jones and single-variable HOMFLY polynomials of the trace closure of a braid at any root of unity.

VL - 9 U4 - 264-289 UR - http://dl.acm.org/citation.cfm?id=2011787 CP - 3 ER - TY - JOUR T1 - Estimating Jones polynomials is a complete problem for one clean qubit JF - Quantum Information & Computation Y1 - 2008 A1 - Peter W. Shor A1 - Stephen P. Jordan AB -It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems. Here we show that evaluating a certain approximation to the Jones polynomial at a fifth root of unity for the trace closure of a braid is a complete problem for the one clean qubit complexity class. That is, a one clean qubit computer can approximate these Jones polynomials in time polynomial in both the number of strands and number of crossings, and the problem of simulating a one clean qubit computer is reducible to approximating the Jones polynomial of the trace closure of a braid.

VL - 8 U4 - 681-714 UR - http://dl.acm.org/citation.cfm?id=2017011.2017012 CP - 8 ER - TY - JOUR T1 - Fast quantum algorithms for approximating some irreducible representations of groups Y1 - 2008 A1 - Stephen P. Jordan AB - We consider the quantum complexity of estimating matrix elements of unitary irreducible representations of groups. For several finite groups including the symmetric group, quantum Fourier transforms yield efficient solutions to this problem. Furthermore, quantum Schur transforms yield efficient solutions for certain irreducible representations of the unitary group. Beyond this, we obtain poly(n)-time quantum algorithms for approximating matrix elements from all the irreducible representations of the alternating group A_n, and all the irreducible representations of polynomial highest weight of U(n), SU(n), and SO(n). These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters. UR - http://arxiv.org/abs/0811.0562v2 ER - TY - JOUR T1 - Perturbative Gadgets at Arbitrary Orders JF - Physical Review A Y1 - 2008 A1 - Stephen P. Jordan A1 - Edward Farhi AB - Adiabatic quantum algorithms are often most easily formulated using many-body interactions. However, experimentally available interactions are generally two-body. In 2004, Kempe, Kitaev, and Regev introduced perturbative gadgets, by which arbitrary three-body effective interactions can be obtained using Hamiltonians consisting only of two-body interactions. These three-body effective interactions arise from the third order in perturbation theory. Since their introduction, perturbative gadgets have become a standard tool in the theory of quantum computation. Here we construct generalized gadgets so that one can directly obtain arbitrary k-body effective interactions from two-body Hamiltonians. These effective interactions arise from the kth order in perturbation theory. VL - 77 UR - http://arxiv.org/abs/0802.1874v4 CP - 6 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.77.062329 ER - TY - JOUR T1 - Polynomial-time quantum algorithm for the simulation of chemical dynamics JF - Proceedings of the National Academy of Sciences Y1 - 2008 A1 - Ivan Kassal A1 - Stephen P. Jordan A1 - Peter J. Love A1 - Masoud Mohseni A1 - Alán Aspuru-Guzik AB - The computational cost of exact methods for quantum simulation using classical computers grows exponentially with system size. As a consequence, these techniques can only be applied to small systems. By contrast, we demonstrate that quantum computers could exactly simulate chemical reactions in polynomial time. Our algorithm uses the split-operator approach and explicitly simulates all electron-nuclear and inter-electronic interactions in quadratic time. Surprisingly, this treatment is not only more accurate than the Born-Oppenheimer approximation, but faster and more efficient as well, for all reactions with more than about four atoms. This is the case even though the entire electronic wavefunction is propagated on a grid with appropriately short timesteps. Although the preparation and measurement of arbitrary states on a quantum computer is inefficient, here we demonstrate how to prepare states of chemical interest efficiently. We also show how to efficiently obtain chemically relevant observables, such as state-to-state transition probabilities and thermal reaction rates. Quantum computers using these techniques could outperform current classical computers with one hundred qubits. VL - 105 U4 - 18681 - 18686 UR - http://arxiv.org/abs/0801.2986v3 CP - 48 J1 - Proceedings of the National Academy of Sciences U5 - 10.1073/pnas.0808245105 ER - TY - JOUR T1 - Quantum Computation Beyond the Circuit Model Y1 - 2008 A1 - Stephen P. Jordan AB - The quantum circuit model is the most widely used model of quantum computation. It provides both a framework for formulating quantum algorithms and an architecture for the physical construction of quantum computers. However, several other models of quantum computation exist which provide useful alternative frameworks for both discovering new quantum algorithms and devising new physical implementations of quantum computers. In this thesis, I first present necessary background material for a general physics audience and discuss existing models of quantum computation. Then, I present three results relating to various models of quantum computation: a scheme for improving the intrinsic fault tolerance of adiabatic quantum computers using quantum error detecting codes, a proof that a certain problem of estimating Jones polynomials is complete for the one clean qubit complexity class, and a generalization of perturbative gadgets which allows k-body interactions to be directly simulated using 2-body interactions. Lastly, I discuss general principles regarding quantum computation that I learned in the course of my research, and using these principles I propose directions for future research. UR - http://arxiv.org/abs/0809.2307v1 ER - TY - JOUR T1 - Error correcting codes for adiabatic quantum computation JF - Physical Review A Y1 - 2006 A1 - Stephen P. Jordan A1 - Edward Farhi A1 - Peter W. Shor AB - Recently, there has been growing interest in using adiabatic quantum computation as an architecture for experimentally realizable quantum computers. One of the reasons for this is the idea that the energy gap should provide some inherent resistance to noise. It is now known that universal quantum computation can be achieved adiabatically using 2-local Hamiltonians. The energy gap in these Hamiltonians scales as an inverse polynomial in the problem size. Here we present stabilizer codes which can be used to produce a constant energy gap against 1-local and 2-local noise. The corresponding fault-tolerant universal Hamiltonians are 4-local and 6-local respectively, which is the optimal result achievable within this framework. VL - 74 UR - http://arxiv.org/abs/quant-ph/0512170v3 CP - 5 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.74.052322 ER - TY - JOUR T1 - Fast quantum algorithm for numerical gradient estimation JF - Physical Review Letters Y1 - 2005 A1 - Stephen P. Jordan AB - Given a blackbox for f, a smooth real scalar function of d real variables, one wants to estimate the gradient of f at a given point with n bits of precision. On a classical computer this requires a minimum of d+1 blackbox queries, whereas on a quantum computer it requires only one query regardless of d. The number of bits of precision to which f must be evaluated matches the classical requirement in the limit of large n. VL - 95 UR - http://arxiv.org/abs/quant-ph/0405146v2 CP - 5 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.95.050501 ER -