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.

%8 05/25/2019 %G eng %U https://arxiv.org/abs/1905.07461 %0 Journal Article %J Phys. Rev. A %D 2019 %T Quantum Algorithm for Simulating the Wave Equation %A Pedro C.S. Costa %A Stephen P. Jordan %A Aaron Ostrander %XWe 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.

%B Phys. Rev. A %V 99 %8 03/24/2019 %G eng %U https://arxiv.org/abs/1711.05394 %N 012323 %R https://doi.org/10.1103/PhysRevA.99.012323 %0 Journal Article %J Quantum %D 2018 %T BQP-completeness of Scattering in Scalar Quantum Field Theory %A Stephen P. Jordan %A Hari Krovi %A Keith S. M. Lee %A John Preskill %XRecent 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.

%B Quantum %V 2 %P 44 %8 2018/01/08 %G eng %U https://quantum-journal.org/papers/q-2018-01-08-44/ %R 10.22331/q-2018-01-08-44 %0 Journal Article %J Physical Review A %D 2018 %T Diffusion Monte Carlo Versus Adiabatic Computation for Local Hamiltonians %A Jacob Bringewatt %A William Dorland %A Stephen P. Jordan %A Alan Mink %XMost 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.

%B Physical Review A %V 97 %P 022323 %8 2018/02/15 %G eng %U https://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.022323 %N 2 %R 10.1103/PhysRevA.97.022323 %0 Journal Article %J IEEE Security & Privacy %D 2018 %T Quantum Cryptanalysis: Shor, Grover, and Beyond %A Stephen P. Jordan %A Yi-Kai Liu %B IEEE Security & Privacy %V 16 %P 14-21 %8 2018/09 %G eng %N 5 %R 10.1109/MSP.2018.3761719 %0 Journal Article %D 2017 %T Experimentally Generated Random Numbers Certified by the Impossibility of Superluminal Signaling %A Peter Bierhorst %A Emanuel Knill %A Scott Glancy %A Alan Mink %A Stephen P. Jordan %A Andrea Rommal %A Yi-Kai Liu %A Bradley Christensen %A Sae Woo Nam %A Lynden K. Shalm %XRandom 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.

%8 2017/02/16 %G eng %U https://arxiv.org/abs/1702.05178# %0 Journal Article %J Physical Review D %D 2017 %T Fast optimization algorithms and the cosmological constant %A Ning Bao %A Raphael Bousso %A Stephen P. Jordan %A Brad Lackey %XDenef 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.

%B Physical Review D %V 96 %P 103512 %8 2017/11/13 %G eng %U https://arxiv.org/abs/1706.08503 %N 10 %R 10.1103/PhysRevD.96.103512 %0 Journal Article %J Physical Review A %D 2017 %T Fast quantum computation at arbitrarily low energy %A Stephen P. Jordan %XOne 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.

%B Physical Review A %V 95 %P 032305 %8 2017/03/06 %G eng %U http://link.aps.org/doi/10.1103/PhysRevA.95.032305 %R 10.1103/PhysRevA.95.032305 %0 Journal Article %J Journal of Mathematical Analysis and Applications %D 2017 %T Modulus of continuity eigenvalue bounds for homogeneous graphs and convex subgraphs with applications to quantum Hamiltonians %A Michael Jarret %A Stephen P. Jordan %XWe 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.

%B Journal of Mathematical Analysis and Applications %V 452 %P 1269-1290 %8 2017/03/03 %G eng %U http://www.sciencedirect.com/science/article/pii/S0022247X1730272X %N 2 %R 10.1016/j.jmaa.2017.03.030 %0 Journal Article %J Physical Review A %D 2016 %T Adiabatic optimization versus diffusion Monte Carlo %A Michael Jarret %A Stephen P. Jordan %A Brad Lackey %XMost 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.

%B Physical Review A %V 94 %P 042318 %8 2016/07/12 %G eng %U https://arxiv.org/abs/1607.03389 %0 Journal Article %J XRDS %D 2016 %T Black Holes, Quantum Mechanics, and the Limits of Polynomial-time Computability %A Stephen P. Jordan %XWhich 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.

%B XRDS %V 23 %P 30–33 %8 2016/09/20 %G eng %U http://doi.acm.org/10.1145/2983539 %R 10.1145/2983539 %0 Journal Article %J Physical Review Letters %D 2016 %T Grover search and the no-signaling principle %A Ning Bao %A Adam Bouland %A Stephen P. Jordan %XFrom 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.

%B Physical Review Letters %V 117 %P 120501 %8 2016/09/14 %G eng %U http://arxiv.org/abs/1511.00657 %0 Journal Article %J Journal of Physics A %D 2016 %T Yang-Baxter operators need quantum entanglement to distinguish knots %A Gorjan Alagic %A Michael Jarret %A Stephen P. Jordan %X 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. %B Journal of Physics A %V 49 %P 075203 %8 2016/01/12 %G eng %U http://arxiv.org/abs/1507.05979 %N 7 %R 10.1088/1751-8113/49/7/075203 %0 Journal Article %J Quantum Information and Computation %D 2015 %T Adiabatic optimization without local minima %A Michael Jarret %A Stephen P. Jordan %X 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. %B Quantum Information and Computation %V 15 %P 181-199 %8 2015/05/01 %G eng %U http://arxiv.org/abs/1405.7552 %N 3-4 %! Quantum Information and Computation %0 Journal Article %J 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) %D 2014 %T Classical simulation of Yang-Baxter gates %A Gorjan Alagic %A Aniruddha Bapat %A Stephen P. Jordan %X 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. %B 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) %V 27 %P 161-175 %8 2014/07/05 %G eng %U http://arxiv.org/abs/1407.1361v1 %! 9th Conference on the Theory of Quantum Computation %R 10.4230/LIPIcs.TQC.2014.161 %0 Journal Article %J Journal of Mathematical Physics %D 2014 %T The Fundamental Gap for a Class of Schrödinger Operators on Path and Hypercube Graphs %A Michael Jarret %A Stephen P. Jordan %X 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. %B Journal of Mathematical Physics %V 55 %P 052104 %8 2014/03/06 %G eng %U http://arxiv.org/abs/1403.1473v1 %N 5 %! J. Math. Phys. %R 10.1063/1.4878120 %0 Conference Proceedings %B In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC14) %D 2014 %T Partial-indistinguishability obfuscation using braids %A Gorjan Alagic %A Stacey Jeffery %A Stephen P. Jordan %XAn 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.

%B In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC14) %8 2014/08/21 %G eng %U http://arxiv.org/abs/1212.6358 %0 Journal Article %D 2014 %T Quantum Algorithms for Fermionic Quantum Field Theories %A Stephen P. Jordan %A Keith S. M. Lee %A John Preskill %X 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. %8 2014/04/28 %G eng %U http://arxiv.org/abs/1404.7115v1 %0 Journal Article %J Quantum Information and Computation %D 2014 %T Quantum Computation of Scattering in Scalar Quantum Field Theories %A Stephen P. Jordan %A Keith S. M. Lee %A John Preskill %X 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. %B Quantum Information and Computation %V 14 %P 1014-1080 %8 2014/09/01 %G eng %U http://arxiv.org/abs/1112.4833v1 %N 11-12 %! Quantum Information and Computation 14 %0 Journal Article %J Quantum Information Computation %D 2014 %T Strong Equivalence of Reversible Circuits is coNP-complete %A Stephen P. Jordan %K complexity %K reversible circuits %XIt 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.

%B Quantum Information Computation %V 14 %P 1302–1307 %8 2014/11/01 %G eng %U http://dl.acm.org/citation.cfm?id=2685179.2685182 %0 Journal Article %J Physical Review A %D 2013 %T Testing quantum expanders is co-QMA-complete %A Adam D. Bookatz %A Stephen P. Jordan %A Yi-Kai Liu %A Pawel Wocjan %X 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. %B Physical Review A %V 87 %8 2013/4/15 %G eng %U http://arxiv.org/abs/1210.0787v2 %N 4 %! Phys. Rev. A %R 10.1103/PhysRevA.87.042317 %0 Journal Article %J Quantum Information and Computation %D 2012 %T Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems %A Stephen P. Jordan %A Hirotada Kobayashi %A Daniel Nagaj %A Harumichi Nishimura %X 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. %B Quantum Information and Computation %V 12 %P 461-471 %8 2012/05/01 %G eng %U http://arxiv.org/abs/1111.5306v2 %N 5-6 %! Quantum Information and Computation Vol. 12 No. 5/6 pg. 461-471 (2012) %0 Journal Article %J Science %D 2012 %T Quantum Algorithms for Quantum Field Theories %A Stephen P. Jordan %A Keith S. M. Lee %A John Preskill %X 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. %B Science %V 336 %P 1130 - 1133 %8 2012/05/31 %G eng %U http://arxiv.org/abs/1111.3633v2 %N 6085 %! Science %R 10.1126/science.1217069 %0 Conference Proceedings %B In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC11) %D 2011 %T Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit %A Stephen P. Jordan %A Gorjan Alagic %XThe 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.

%B In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC11) %8 2011/05/31 %G eng %U http://arxiv.org/abs/1105.5100 %0 Journal Article %J Physical Review A %D 2010 %T Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation %A Gorjan Alagic %A Stephen P. Jordan %A Robert Koenig %A Ben W. Reichardt %X 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. %B Physical Review A %V 82 %8 2010/10/8 %G eng %U http://arxiv.org/abs/1003.0923v1 %N 4 %! Phys. Rev. A %R 10.1103/PhysRevA.82.040302 %0 Journal Article %D 2010 %T On the degeneracy of SU(3)k topological phases %A Stephen P. Jordan %A Toufik Mansour %A Simone Severini %XThe 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.

%8 2010/09/01 %G eng %U http://arxiv.org/abs/1009.0114v1 %0 Journal Article %J Quantum Information & Computation %D 2010 %T Permutational Quantum Computing %A Stephen P. Jordan %XIn 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.

%B Quantum Information & Computation %V 10 %P 470-497 %8 2010/05/01 %G eng %U http://dl.acm.org/citation.cfm?id=2011369 %N 5 %! Quantum Information and Computation Vol. 10 pg. 470 (2010) %0 Journal Article %J Physical Review A %D 2010 %T QMA-complete problems for stoquastic Hamiltonians and Markov matrices %A Stephen P. Jordan %A David Gosset %A Peter J. Love %X 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. %B Physical Review A %V 81 %8 2010/3/29 %G eng %U http://arxiv.org/abs/0905.4755v2 %N 3 %! Phys. Rev. A %R 10.1103/PhysRevA.81.032331 %0 Journal Article %J Theory of Computing %D 2009 %T Discrete-query quantum algorithm for NAND trees %A Andrew M. Childs %A Richard Cleve %A Stephen P. Jordan %A David Yeung %X 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. %B Theory of Computing %V 5 %P 119 - 123 %8 2009/07/01 %G eng %U http://arxiv.org/abs/quant-ph/0702160v1 %N 1 %! Theory of Comput. %R 10.4086/toc.2009.v005a005 %0 Journal Article %J Physical Review A %D 2009 %T Efficient quantum circuits for arbitrary sparse unitaries %A Stephen P. Jordan %A Pawel Wocjan %X 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. %B Physical Review A %V 80 %8 2009/12/1 %G eng %U http://arxiv.org/abs/0904.2211v2 %N 6 %! Phys. Rev. A %R 10.1103/PhysRevA.80.062301 %0 Journal Article %D 2009 %T Efficient quantum processing of ideals in finite rings %A Pawel M. Wocjan %A Stephen P. Jordan %A Hamed Ahmadi %A Joseph P. Brennan %X 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. %8 2009/07/31 %G eng %U http://arxiv.org/abs/0908.0022v1 %0 Journal Article %J Quantum Information and Computation %D 2009 %T Estimating Jones and HOMFLY polynomials with One Clean Qubit %A Stephen P. Jordan %A Pawel Wocjan %XThe 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.

%B Quantum Information and Computation %V 9 %P 264-289 %8 2009/03/01 %G eng %U http://dl.acm.org/citation.cfm?id=2011787 %N 3 %0 Journal Article %J Quantum Information & Computation %D 2008 %T Estimating Jones polynomials is a complete problem for one clean qubit %A Peter W. Shor %A Stephen P. Jordan %XIt 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.

%B Quantum Information & Computation %V 8 %P 681-714 %8 2008/09/01 %G eng %U http://dl.acm.org/citation.cfm?id=2017011.2017012 %N 8 %0 Journal Article %D 2008 %T Fast quantum algorithms for approximating some irreducible representations of groups %A Stephen P. Jordan %X 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. %8 2008/11/04 %G eng %U http://arxiv.org/abs/0811.0562v2 %0 Journal Article %J Physical Review A %D 2008 %T Perturbative Gadgets at Arbitrary Orders %A Stephen P. Jordan %A Edward Farhi %X 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. %B Physical Review A %V 77 %8 2008/6/19 %G eng %U http://arxiv.org/abs/0802.1874v4 %N 6 %! Phys. Rev. A %R 10.1103/PhysRevA.77.062329 %0 Journal Article %J Proceedings of the National Academy of Sciences %D 2008 %T Polynomial-time quantum algorithm for the simulation of chemical dynamics %A Ivan Kassal %A Stephen P. Jordan %A Peter J. Love %A Masoud Mohseni %A Alán Aspuru-Guzik %X 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. %B Proceedings of the National Academy of Sciences %V 105 %P 18681 - 18686 %8 2008/11/24 %G eng %U http://arxiv.org/abs/0801.2986v3 %N 48 %! Proceedings of the National Academy of Sciences %R 10.1073/pnas.0808245105 %0 Journal Article %D 2008 %T Quantum Computation Beyond the Circuit Model %A Stephen P. Jordan %X 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. %8 2008/09/13 %G eng %U http://arxiv.org/abs/0809.2307v1 %0 Journal Article %J Physical Review A %D 2006 %T Error correcting codes for adiabatic quantum computation %A Stephen P. Jordan %A Edward Farhi %A Peter W. Shor %X 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. %B Physical Review A %V 74 %8 2006/11/14 %G eng %U http://arxiv.org/abs/quant-ph/0512170v3 %N 5 %! Phys. Rev. A %R 10.1103/PhysRevA.74.052322 %0 Journal Article %J Physical Review Letters %D 2005 %T Fast quantum algorithm for numerical gradient estimation %A Stephen P. Jordan %X 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. %B Physical Review Letters %V 95 %8 2005/7/28 %G eng %U http://arxiv.org/abs/quant-ph/0405146v2 %N 5 %! Phys. Rev. Lett. %R 10.1103/PhysRevLett.95.050501