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.

}, url = {https://arxiv.org/abs/1905.07461}, author = {Jacob Bringewatt and William Dorland and Stephen P. Jordan} } @article {2131, title = {Quantum Algorithm for Simulating the Wave Equation}, journal = {Phys. Rev. A }, volume = {99 }, year = {2019}, month = {03/24/2019}, abstract = {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\&$\#$39;s equations.

}, doi = {https://doi.org/10.1103/PhysRevA.99.012323}, url = {https://arxiv.org/abs/1711.05394}, author = {Pedro C.S. Costa and Stephen P. Jordan and Aaron Ostrander} } @article {1949, title = {BQP-completeness of Scattering in Scalar Quantum Field Theory}, journal = {Quantum}, volume = {2}, year = {2018}, month = {2018/01/08}, pages = {44}, abstract = {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.

}, doi = {10.22331/q-2018-01-08-44}, url = {https://quantum-journal.org/papers/q-2018-01-08-44/}, author = {Stephen P. Jordan and Hari Krovi and Keith S. M. Lee and John Preskill} } @article {2047, title = {Diffusion Monte Carlo Versus Adiabatic Computation for Local Hamiltonians}, journal = {Physical Review A}, volume = {97}, year = {2018}, month = {2018/02/15}, pages = {022323}, abstract = {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.

}, doi = {10.1103/PhysRevA.97.022323}, url = {https://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.022323}, author = {Jacob Bringewatt and William Dorland and Stephen P. Jordan and Alan Mink} } @article {2326, title = {Quantum Cryptanalysis: Shor, Grover, and Beyond}, journal = {IEEE Security \& Privacy }, volume = {16}, year = {2018}, month = {2018/09}, pages = {14-21}, doi = {10.1109/MSP.2018.3761719}, author = {Stephen P. Jordan and Yi-Kai Liu} } @article {1945, title = {Experimentally Generated Random Numbers Certified by the Impossibility of Superluminal Signaling}, year = {2017}, month = {2017/02/16}, abstract = {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.

}, url = {https://arxiv.org/abs/1702.05178$\#$}, author = {Peter Bierhorst and Emanuel Knill and Scott Glancy and Alan Mink and Stephen P. Jordan and Andrea Rommal and Yi-Kai Liu and Bradley Christensen and Sae Woo Nam and Lynden K. Shalm} } @article {1991, title = {Fast optimization algorithms and the cosmological constant}, journal = {Physical Review D}, volume = {96}, year = {2017}, month = {2017/11/13}, pages = {103512}, abstract = {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.

}, doi = {10.1103/PhysRevD.96.103512}, url = {https://arxiv.org/abs/1706.08503}, author = {Ning Bao and Raphael Bousso and Stephen P. Jordan and Brad Lackey} } @article {1948, title = {Fast quantum computation at arbitrarily low energy}, journal = {Physical Review A}, volume = {95}, year = {2017}, month = {2017/03/06}, pages = {032305}, abstract = {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\&$\#$39;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.

}, doi = {10.1103/PhysRevA.95.032305}, url = {http://link.aps.org/doi/10.1103/PhysRevA.95.032305}, author = {Stephen P. Jordan} } @article {1392, title = {Modulus of continuity eigenvalue bounds for homogeneous graphs and convex subgraphs with applications to quantum Hamiltonians}, journal = {Journal of Mathematical Analysis and Applications}, volume = {452}, year = {2017}, month = {2017/03/03}, pages = {1269-1290}, abstract = {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.

}, doi = {10.1016/j.jmaa.2017.03.030}, url = {http://www.sciencedirect.com/science/article/pii/S0022247X1730272X}, author = {Michael Jarret and Stephen P. Jordan} } @article {1813, title = {Adiabatic optimization versus diffusion Monte Carlo}, journal = {Physical Review A}, volume = {94}, year = {2016}, month = {2016/07/12}, pages = {042318}, abstract = {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.

}, url = {https://arxiv.org/abs/1607.03389}, author = {Michael Jarret and Stephen P. Jordan and Brad Lackey} } @article {1950, title = {Black Holes, Quantum Mechanics, and the Limits of Polynomial-time Computability}, journal = {XRDS}, volume = {23}, year = {2016}, month = {2016/09/20}, pages = {30{\textendash}33}, abstract = {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.

}, issn = {1528-4972}, doi = {10.1145/2983539}, url = {http://doi.acm.org/10.1145/2983539}, author = {Stephen P. Jordan} } @article {1597, title = {Grover search and the no-signaling principle}, journal = {Physical Review Letters}, volume = {117}, year = {2016}, month = {2016/09/14}, pages = {120501}, abstract = {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\&$\#$39;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\&$\#$39;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\&$\#$39;s algorithm.

}, url = {http://arxiv.org/abs/1511.00657}, author = {Ning Bao and Adam Bouland and Stephen P. Jordan} } @article {1393, title = {Yang-Baxter operators need quantum entanglement to distinguish knots}, journal = {Journal of Physics A}, volume = {49}, year = {2016}, month = {2016/01/12}, pages = {075203}, abstract = { 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. }, doi = {10.1088/1751-8113/49/7/075203}, url = {http://arxiv.org/abs/1507.05979}, author = {Gorjan Alagic and Michael Jarret and Stephen P. Jordan} } @article {1390, title = {Adiabatic optimization without local minima}, journal = {Quantum Information and Computation}, volume = {15}, year = {2015}, month = {2015/05/01}, pages = {181-199}, abstract = { 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. }, url = {http://arxiv.org/abs/1405.7552}, author = {Michael Jarret and Stephen P. Jordan} } @article {1391, title = {Classical simulation of Yang-Baxter gates}, journal = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)}, volume = {27}, year = {2014}, month = {2014/07/05}, pages = {161-175}, abstract = { 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. }, doi = {10.4230/LIPIcs.TQC.2014.161}, url = {http://arxiv.org/abs/1407.1361v1}, author = {Gorjan Alagic and Aniruddha Bapat and Stephen P. Jordan} } @article {1389, title = {The Fundamental Gap for a Class of Schr{\"o}dinger Operators on Path and Hypercube Graphs}, journal = {Journal of Mathematical Physics}, volume = {55}, year = {2014}, month = {2014/03/06}, pages = {052104}, abstract = { 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. }, doi = {10.1063/1.4878120}, url = {http://arxiv.org/abs/1403.1473v1}, author = {Michael Jarret and Stephen P. Jordan} } @proceedings {1388, title = {Partial-indistinguishability obfuscation using braids}, journal = {In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC14)}, year = {2014}, month = {2014/08/21}, abstract = {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.

}, url = {http://arxiv.org/abs/1212.6358}, author = {Gorjan Alagic and Stacey Jeffery and Stephen P. Jordan} } @article {1403, title = {Quantum Algorithms for Fermionic Quantum Field Theories}, year = {2014}, month = {2014/04/28}, abstract = { 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. }, url = {http://arxiv.org/abs/1404.7115v1}, author = {Stephen P. Jordan and Keith S. M. Lee and John Preskill} } @article {1395, title = {Quantum Computation of Scattering in Scalar Quantum Field Theories}, journal = {Quantum Information and Computation}, volume = {14}, year = {2014}, month = {2014/09/01}, pages = {1014-1080}, abstract = { 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. }, url = {http://arxiv.org/abs/1112.4833v1}, author = {Stephen P. Jordan and Keith S. M. Lee and John Preskill} } @article {1871, title = {Strong Equivalence of Reversible Circuits is coNP-complete}, journal = {Quantum Information Computation}, volume = {14}, year = {2014}, month = {2014/11/01}, pages = {1302{\textendash}1307}, abstract = {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\&$\#$39;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.

}, keywords = {complexity, reversible circuits}, issn = {1533-7146}, url = {http://dl.acm.org/citation.cfm?id=2685179.2685182}, author = {Stephen P. Jordan} } @article {1402, title = {Testing quantum expanders is co-QMA-complete}, journal = {Physical Review A}, volume = {87}, year = {2013}, month = {2013/4/15}, abstract = { 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. }, doi = {10.1103/PhysRevA.87.042317}, url = {http://arxiv.org/abs/1210.0787v2}, author = {Adam D. Bookatz and Stephen P. Jordan and Yi-Kai Liu and Pawel Wocjan} } @article {1398, title = {Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems}, journal = {Quantum Information and Computation}, volume = {12}, year = {2012}, month = {2012/05/01}, pages = {461-471}, abstract = { 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. }, url = {http://arxiv.org/abs/1111.5306v2}, author = {Stephen P. Jordan and Hirotada Kobayashi and Daniel Nagaj and Harumichi Nishimura} } @article {1397, title = {Quantum Algorithms for Quantum Field Theories}, journal = {Science}, volume = {336}, year = {2012}, month = {2012/05/31}, pages = {1130 - 1133}, abstract = { 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. }, doi = {10.1126/science.1217069}, url = {http://arxiv.org/abs/1111.3633v2}, author = {Stephen P. Jordan and Keith S. M. Lee and John Preskill} } @proceedings {1387, title = {Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit}, journal = { In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC11)}, year = {2011}, month = {2011/05/31}, abstract = {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.

}, url = {http://arxiv.org/abs/1105.5100}, author = {Stephen P. Jordan and Gorjan Alagic} } @article {1401, title = {Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation }, journal = {Physical Review A}, volume = {82}, year = {2010}, month = {2010/10/8}, abstract = { 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. }, doi = {10.1103/PhysRevA.82.040302}, url = {http://arxiv.org/abs/1003.0923v1}, author = {Gorjan Alagic and Stephen P. Jordan and Robert Koenig and Ben W. Reichardt} } @article {1385, title = {On the degeneracy of SU(3)k topological phases}, year = {2010}, month = {2010/09/01}, abstract = {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.

}, url = {http://arxiv.org/abs/1009.0114v1}, author = {Stephen P. Jordan and Toufik Mansour and Simone Severini} } @article {1380, title = {Permutational Quantum Computing}, journal = {Quantum Information \& Computation}, volume = {10}, year = {2010}, month = {2010/05/01}, pages = {470-497}, abstract = {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.

}, url = {http://dl.acm.org/citation.cfm?id=2011369}, author = {Stephen P. Jordan} } @article {1396, title = {QMA-complete problems for stoquastic Hamiltonians and Markov matrices}, journal = {Physical Review A}, volume = {81}, year = {2010}, month = {2010/3/29}, abstract = { 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. }, doi = {10.1103/PhysRevA.81.032331}, url = {http://arxiv.org/abs/0905.4755v2}, author = {Stephen P. Jordan and David Gosset and Peter J. Love} } @article {1254, title = {Discrete-query quantum algorithm for NAND trees}, journal = {Theory of Computing}, volume = {5}, year = {2009}, month = {2009/07/01}, pages = {119 - 123}, abstract = { 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. }, doi = {10.4086/toc.2009.v005a005}, url = {http://arxiv.org/abs/quant-ph/0702160v1}, author = {Andrew M. Childs and Richard Cleve and Stephen P. Jordan and David Yeung} } @article {1386, title = {Efficient quantum circuits for arbitrary sparse unitaries}, journal = {Physical Review A}, volume = {80}, year = {2009}, month = {2009/12/1}, abstract = { 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. }, doi = {10.1103/PhysRevA.80.062301}, url = {http://arxiv.org/abs/0904.2211v2}, author = {Stephen P. Jordan and Pawel Wocjan} } @article {1400, title = {Efficient quantum processing of ideals in finite rings}, year = {2009}, month = {2009/07/31}, abstract = { 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. }, url = {http://arxiv.org/abs/0908.0022v1}, author = {Pawel M. Wocjan and Stephen P. Jordan and Hamed Ahmadi and Joseph P. Brennan} } @article {1384, title = {Estimating Jones and HOMFLY polynomials with One Clean Qubit}, journal = {Quantum Information and Computation}, volume = {9}, year = {2009}, month = {2009/03/01}, pages = {264-289}, abstract = {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.

}, url = {http://dl.acm.org/citation.cfm?id=2011787}, author = {Stephen P. Jordan and Pawel Wocjan} } @article {1382, title = {Estimating Jones polynomials is a complete problem for one clean qubit}, journal = {Quantum Information \& Computation}, volume = {8}, year = {2008}, month = {2008/09/01}, pages = {681-714}, abstract = {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.

}, url = {http://dl.acm.org/citation.cfm?id=2017011.2017012}, author = {Peter W. Shor and Stephen P. Jordan} } @article {1379, title = {Fast quantum algorithms for approximating some irreducible representations of groups }, year = {2008}, month = {2008/11/04}, abstract = { 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. }, url = {http://arxiv.org/abs/0811.0562v2}, author = {Stephen P. Jordan} } @article {1383, title = {Perturbative Gadgets at Arbitrary Orders}, journal = {Physical Review A}, volume = {77}, year = {2008}, month = {2008/6/19}, abstract = { 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. }, doi = {10.1103/PhysRevA.77.062329}, url = {http://arxiv.org/abs/0802.1874v4}, author = {Stephen P. Jordan and Edward Farhi} } @article {1399, title = {Polynomial-time quantum algorithm for the simulation of chemical dynamics }, journal = {Proceedings of the National Academy of Sciences}, volume = {105}, year = {2008}, month = {2008/11/24}, pages = {18681 - 18686}, abstract = { 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. }, doi = {10.1073/pnas.0808245105}, url = {http://arxiv.org/abs/0801.2986v3}, author = {Ivan Kassal and Stephen P. Jordan and Peter J. Love and Masoud Mohseni and Al{\'a}n Aspuru-Guzik} } @article {1378, title = {Quantum Computation Beyond the Circuit Model}, year = {2008}, month = {2008/09/13}, abstract = { 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. }, url = {http://arxiv.org/abs/0809.2307v1}, author = {Stephen P. Jordan} } @article {1394, title = {Error correcting codes for adiabatic quantum computation}, journal = {Physical Review A}, volume = {74}, year = {2006}, month = {2006/11/14}, abstract = { 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. }, doi = {10.1103/PhysRevA.74.052322}, url = {http://arxiv.org/abs/quant-ph/0512170v3}, author = {Stephen P. Jordan and Edward Farhi and Peter W. Shor} } @article {1377, title = {Fast quantum algorithm for numerical gradient estimation}, journal = {Physical Review Letters}, volume = {95}, year = {2005}, month = {2005/7/28}, abstract = { 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. }, doi = {10.1103/PhysRevLett.95.050501}, url = {http://arxiv.org/abs/quant-ph/0405146v2}, author = {Stephen P. Jordan} }