01810nas a2200121 4500008004100000245006600041210006600107260001400173520141900187100002101606700002401627856003701651 2021 eng d00aPreparing Renormalization Group Fixed Points on NISQ Hardware0 aPreparing Renormalization Group Fixed Points on NISQ Hardware c9/20/20213 a

Noisy intermediate-scale quantum (NISQ) hardware is typically limited to low-depth quantum circuits to limit the number of opportunities for introduction of error by unreliable quantum gates. A less-explored alternative approach is to repeatedly apply a quantum channel with a desired quantum state as a stable fixed point. Increased circuit depth can in this case be beneficial rather than harmful due to dissipative self-correction. The quantum channels constructed from MERA circuits can be interpreted in terms of the renormalization group(RG), and their fixed points are RG fixed points, i.e. scale-invariant systems such as conformal field theories. Here, building upon the theoretical proposal of Kim and Swingle, we numerically and experimentally study the robust preparation of the ground state of the critical Ising model using circuits adapted from the work of Evenbly and White. The experimental implementation exhibits self-correction through renormalization seen in the convergence and stability of local observables, and makes essential use of the ability to measure and reset individual qubits afforded by the "quantum CCD" architecture of the Honeywell ion-trap. We also numerically test error mitigation by zero-noise extrapolation schemes specially adapted for renormalization circuits, which are able to outperform typical extrapolation schemes using lower gate overhead. 

1 aSewell, Troy, J.1 aJordan, Stephen, P. uhttps://arxiv.org/abs/2109.0978701814nas a2200121 4500008004100000245006700041210006700108260001400175520142100189100002101610700002401631856003701655 2020 eng d00aApproximate optimization of MAXCUT with a local spin algorithm0 aApproximate optimization of MAXCUT with a local spin algorithm c8/13/20203 a

Local tensor methods are a class of optimization algorithms that was introduced in [Hastings,arXiv:1905.07047v2][1] as a classical analogue of the quantum approximate optimization algorithm (QAOA). These algorithms treat the cost function as a Hamiltonian on spin degrees of freedom and simulate the relaxation of the system to a low energy configuration using local update rules on the spins. Whereas the emphasis in [1] was on theoretical worst-case analysis, we here investigate performance in practice through benchmarking experiments on instances of the MAXCUT problem.Through heuristic arguments we propose formulas for choosing the hyperparameters of the algorithm which are found to be in good agreement with the optimal choices determined from experiment. We observe that the local tensor method is closely related to gradient descent on a relaxation of maxcut to continuous variables, but consistently outperforms gradient descent in all instances tested. We find time to solution achieved by the local tensor method is highly uncorrelated with that achieved by a widely used commercial optimization package; on some MAXCUT instances the local tensor method beats the commercial solver in time to solution by up to two orders of magnitude and vice-versa. Finally, we argue that the local tensor method closely follows discretized, imaginary-time dynamics of the system under the problem Hamiltonian.

1 aBapat, Aniruddha1 aJordan, Stephen, P. uhttps://arxiv.org/abs/2008.0605401973nas a2200145 4500008004100000245008000041210006900121260001400190490000800204520151100212100002201723700002101745700002401766856003701790 2019 eng d00aPolynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians0 aPolynomial Time Algorithms for Estimating Spectra of Adiabatic H c10/1/20200 v1003 a

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.

1 aBringewatt, Jacob1 aDorland, William1 aJordan, Stephen, P. uhttps://arxiv.org/abs/1905.0746101091nas a2200145 4500008004100000245005500041210005500096260001500151490000800166520066600174100002300840700002400863700002100887856003700908 2019 eng d00aQuantum Algorithm for Simulating the Wave Equation0 aQuantum Algorithm for Simulating the Wave Equation c03/24/20190 v99 3 a

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.

1 aCosta, Pedro, C.S.1 aJordan, Stephen, P.1 aOstrander, Aaron uhttps://arxiv.org/abs/1711.0539401623nas a2200133 4500008004100000245011100041210006900152260001400221520114300235100002601378700002401404700002401428856003701452 2019 eng d00aSite-by-site quantum state preparation algorithm for preparing vacua of fermionic lattice field theories 0 aSitebysite quantum state preparation algorithm for preparing vac c2019/11/83 a

Answering whether quantum computers can efficiently simulate quantum field theories has both theoretical and practical motivation. From the theoretical point of view, it answers the question of whether a hypothetical computer that utilizes quantum field theory would be more powerful than other quantum computers. From the practical point of view, when reliable quantum computers are eventually built, these algorithms can help us better understand the underlying physics that govern our world. In the best known quantum algorithms for simulating quantum field theories, the time scaling is dominated by initial state preparation. In this paper, we exclusively focus on state preparation and present a heuristic algorithm that can prepare the vacuum of fermionic systems in more general cases and more efficiently than previous methods. With our method, state preparation is no longer the bottleneck, as its runtime has the same asymptotic scaling with the desired precision as the remainder of the simulation algorithm. We numerically demonstrate the effectiveness of our proposed method for the 1+1 dimensional Gross-Neveu model.

1 aMoosavian, Ali, Hamed1 aGarrison, James, R.1 aJordan, Stephen, P. uhttps://arxiv.org/abs/1911.0350501856nas a2200169 4500008004100000245006600041210006500107260001500172300000700187490000600194520134900200100002401549700001601573700002201589700001901611856005601630 2018 eng d00aBQP-completeness of Scattering in Scalar Quantum Field Theory0 aBQPcompleteness of Scattering in Scalar Quantum Field Theory c2018/01/08 a440 v23 a

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.

1 aJordan, Stephen, P.1 aKrovi, Hari1 aLee, Keith, S. M.1 aPreskill, John uhttps://quantum-journal.org/papers/q-2018-01-08-44/01752nas a2200169 4500008004100000245007800041210006900119260001500188300001100203490000700214520121000221100002201431700002101453700002401474700001501498856006901513 2018 eng d00aDiffusion Monte Carlo Versus Adiabatic Computation for Local Hamiltonians0 aDiffusion Monte Carlo Versus Adiabatic Computation for Local Ham c2018/02/15 a0223230 v973 a

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.

1 aBringewatt, Jacob1 aDorland, William1 aJordan, Stephen, P.1 aMink, Alan uhttps://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.02232300433nas a2200133 4500008004100000245005200041210004900093260001200142300001000154490000700164100002400171700001600195856008800211 2018 eng d00aQuantum Cryptanalysis: Shor, Grover, and Beyond0 aQuantum Cryptanalysis Shor Grover and Beyond c2018/09 a14-210 v161 aJordan, Stephen, P.1 aLiu, Yi-Kai uhttps://www.quics.umd.edu/publications/quantum-cryptanalysis-shor-grover-and-beyond01575nas a2200217 4500008004100000245010100041210006900142260001500211520089600226100002101122700001901143700001801162700001501180700002401195700001901219700001601238700002501254700001801279700002201297856003801319 2017 eng d00aExperimentally Generated Random Numbers Certified by the Impossibility of Superluminal Signaling0 aExperimentally Generated Random Numbers Certified by the Impossi c2017/02/163 a

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.

1 aBierhorst, Peter1 aKnill, Emanuel1 aGlancy, Scott1 aMink, Alan1 aJordan, Stephen, P.1 aRommal, Andrea1 aLiu, Yi-Kai1 aChristensen, Bradley1 aNam, Sae, Woo1 aShalm, Lynden, K. uhttps://arxiv.org/abs/1702.05178#01300nas a2200169 4500008004100000245006300041210006300104260001500167300001100182490000700193520081800200100001401018700002001032700002401052700001701076856003701093 2017 eng d00aFast optimization algorithms and the cosmological constant0 aFast optimization algorithms and the cosmological constant c2017/11/13 a1035120 v963 a

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.

1 aBao, Ning1 aBousso, Raphael1 aJordan, Stephen, P.1 aLackey, Brad uhttps://arxiv.org/abs/1706.0850322768nas a2200133 45000080041000002450055000412100055000962600015001513000011001664900007001775202237100184100002422555856005522579 2017 eng d00aFast quantum computation at arbitrarily low energy0 aFast quantum computation at arbitrarily low energy c2017/03/06 a0323050 v953 a

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 Th/(2E), 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.

1 aJordan, Stephen, P. uhttp://link.aps.org/doi/10.1103/PhysRevA.95.03230501224nas a2200145 4500008004100000245013100041210006900172260001500241300001400256490000800270520068500278100002000963700002400983856007101007 2017 eng d00aModulus of continuity eigenvalue bounds for homogeneous graphs and convex subgraphs with applications to quantum Hamiltonians0 aModulus of continuity eigenvalue bounds for homogeneous graphs a c2017/03/03 a1269-12900 v4523 a

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.

1 aJarret, Michael1 aJordan, Stephen, P. uhttp://www.sciencedirect.com/science/article/pii/S0022247X1730272X01455nas a2200157 4500008004100000245005600041210005600097260001500153300001100168490000700179520101300186100002001199700002401219700001701243856003701260 2016 eng d00aAdiabatic optimization versus diffusion Monte Carlo0 aAdiabatic optimization versus diffusion Monte Carlo c2016/07/12 a0423180 v943 a

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.

1 aJarret, Michael1 aJordan, Stephen, P.1 aLackey, Brad uhttps://arxiv.org/abs/1607.0338900790nas a2200145 4500008004100000022001400041245008400055210006900139260001500208300001200223490000700235520033900242100002400581856003900605 2016 eng d a1528-497200aBlack Holes, Quantum Mechanics, and the Limits of Polynomial-time Computability0 aBlack Holes Quantum Mechanics and the Limits of Polynomialtime C c2016/09/20 a30–330 v233 a

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.

1 aJordan, Stephen, P. uhttp://doi.acm.org/10.1145/298353901660nas a2200157 4500008004100000245004900041210004800090260001500138300001100153490000800164520123800172100001401410700001801424700002401442856003601466 2016 eng d00aGrover search and the no-signaling principle0 aGrover search and the nosignaling principle c2016/09/14 a1205010 v1173 a

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.

1 aBao, Ning1 aBouland, Adam1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1511.0065701014nas a2200157 4500008004100000245007300041210006900114260001500183300001100198490000700209520054100216100001900757700002000776700002400796856003600820 2016 eng d00aYang-Baxter operators need quantum entanglement to distinguish knots0 aYangBaxter operators need quantum entanglement to distinguish kn c2016/01/12 a0752030 v493 a 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. 1 aAlagic, Gorjan1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1507.0597901350nas a2200145 4500008004100000245004800041210004800089260001500137300001200152490000700164520095400171100002001125700002401145856003501169 2015 eng d00aAdiabatic optimization without local minima0 aAdiabatic optimization without local minima c2015/05/01 a181-1990 v153 a 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. 1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1405.755201280nas a2200157 4500008004100000245004600041210004500087260001500132300001200147490000700159520085500166100001901021700002101040700002401061856003701085 2014 eng d00aClassical simulation of Yang-Baxter gates0 aClassical simulation of YangBaxter gates c2014/07/05 a161-1750 v273 a 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. 1 aAlagic, Gorjan1 aBapat, Aniruddha1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1407.1361v101173nas a2200145 4500008004100000245009200041210007000133260001500203300001100218490000700229520071000236100002000946700002400966856003700990 2014 eng d00aThe Fundamental Gap for a Class of Schrödinger Operators on Path and Hypercube Graphs0 aFundamental Gap for a Class of Schrödinger Operators on Path and c2014/03/06 a0521040 v553 a 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. 1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1403.1473v101518nas a2200133 4500008004100000245005800041210005700099260001500156520111500171100001901286700002001305700002401325856003501349 2014 eng d00aPartial-indistinguishability obfuscation using braids0 aPartialindistinguishability obfuscation using braids c2014/08/213 a

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.

1 aAlagic, Gorjan1 aJeffery, Stacey1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1212.635801013nas a2200133 4500008004100000245006000041210006000101260001500161520060100176100002400777700002200801700001900823856003700842 2014 eng d00aQuantum Algorithms for Fermionic Quantum Field Theories0 aQuantum Algorithms for Fermionic Quantum Field Theories c2014/04/283 a 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. 1 aJordan, Stephen, P.1 aLee, Keith, S. M.1 aPreskill, John uhttp://arxiv.org/abs/1404.7115v101375nas a2200157 4500008004100000245007100041210006900112260001500181300001400196490000700210520089800217100002401115700002201139700001901161856003701180 2014 eng d00aQuantum Computation of Scattering in Scalar Quantum Field Theories0 aQuantum Computation of Scattering in Scalar Quantum Field Theori c2014/09/01 a1014-10800 v143 a 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. 1 aJordan, Stephen, P.1 aLee, Keith, S. M.1 aPreskill, John uhttp://arxiv.org/abs/1112.4833v101364nas a2200169 4500008004100000022001400041245006300055210006200118260001500180300001600195490000700211520085900218653001501077653002401092100002401116856005401140 2014 eng d a1533-714600aStrong Equivalence of Reversible Circuits is coNP-complete0 aStrong Equivalence of Reversible Circuits is coNPcomplete c2014/11/01 a1302–13070 v143 a

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.

10acomplexity10areversible circuits1 aJordan, Stephen, P. uhttp://dl.acm.org/citation.cfm?id=2685179.268518200882nas a2200157 4500008004100000245004900041210004700090260001400137490000700151520044900158100002200607700002400629700001600653700001800669856003700687 2013 eng d00aTesting quantum expanders is co-QMA-complete0 aTesting quantum expanders is coQMAcomplete c2013/4/150 v873 a 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. 1 aBookatz, Adam, D.1 aJordan, Stephen, P.1 aLiu, Yi-Kai1 aWocjan, Pawel uhttp://arxiv.org/abs/1210.0787v201021nas a2200169 4500008004100000245009300041210006900134260001500203300001200218490000700230520048600237100002400723700002400747700001800771700002500789856003700814 2012 eng d00aAchieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems0 aAchieving perfect completeness in classicalwitness quantum Merli c2012/05/01 a461-4710 v123 a 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. 1 aJordan, Stephen, P.1 aKobayashi, Hirotada1 aNagaj, Daniel1 aNishimura, Harumichi uhttp://arxiv.org/abs/1111.5306v201068nas a2200157 4500008004100000245005000041210005000091260001500141300001600156490000800172520062800180100002400808700002200832700001900854856003700873 2012 eng d00aQuantum Algorithms for Quantum Field Theories0 aQuantum Algorithms for Quantum Field Theories c2012/05/31 a1130 - 11330 v3363 a 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. 1 aJordan, Stephen, P.1 aLee, Keith, S. M.1 aPreskill, John uhttp://arxiv.org/abs/1111.3633v201079nas a2200121 4500008004100000245009300041210006900134260001500203520066100218100002400879700001900903856003500922 2011 eng d00aApproximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit0 aApproximating the TuraevViro Invariant of Mapping Tori is Comple c2011/05/313 a

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.

1 aJordan, Stephen, P.1 aAlagic, Gorjan uhttp://arxiv.org/abs/1105.510001327nas a2200157 4500008004100000245009200041210006900133260001400202490000700216520082400223100001901047700002401066700001901090700002301109856003701132 2010 eng d00aApproximating Turaev-Viro 3-manifold invariants is universal for quantum computation 0 aApproximating TuraevViro 3manifold invariants is universal for q c2010/10/80 v823 a 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. 1 aAlagic, Gorjan1 aJordan, Stephen, P.1 aKoenig, Robert1 aReichardt, Ben, W. uhttp://arxiv.org/abs/1003.0923v100869nas a2200133 4500008004100000245005100041210004200092260001500134520048400149100002400633700002000657700002100677856003700698 2010 eng d00aOn the degeneracy of SU(3)k topological phases0 adegeneracy of SU3k topological phases c2010/09/013 a

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.

1 aJordan, Stephen, P.1 aMansour, Toufik1 aSeverini, Simone uhttp://arxiv.org/abs/1009.0114v101293nas a2200133 4500008004100000245003600041210003600077260001500113300001200128490000700140520094200147100002401089856004601113 2010 eng d00aPermutational Quantum Computing0 aPermutational Quantum Computing c2010/05/01 a470-4970 v103 a

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.

1 aJordan, Stephen, P. uhttp://dl.acm.org/citation.cfm?id=201136901051nas a2200145 4500008004100000245007400041210006900115260001400184490000700198520060100205100002400806700001800830700002000848856003700868 2010 eng d00aQMA-complete problems for stoquastic Hamiltonians and Markov matrices0 aQMAcomplete problems for stoquastic Hamiltonians and Markov matr c2010/3/290 v813 a 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. 1 aJordan, Stephen, P.1 aGosset, David1 aLove, Peter, J. uhttp://arxiv.org/abs/0905.4755v200832nas a2200169 4500008004100000245005200041210005100093260001500144300001400159490000600173520035600179100002300535700001900558700002400577700001700601856004400618 2009 eng d00aDiscrete-query quantum algorithm for NAND trees0 aDiscretequery quantum algorithm for NAND trees c2009/07/01 a119 - 1230 v53 a 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. 1 aChilds, Andrew, M.1 aCleve, Richard1 aJordan, Stephen, P.1 aYeung, David uhttp://arxiv.org/abs/quant-ph/0702160v101162nas a2200133 4500008004100000245006200041210006200103260001400165490000700179520076300186100002400949700001800973856003700991 2009 eng d00aEfficient quantum circuits for arbitrary sparse unitaries0 aEfficient quantum circuits for arbitrary sparse unitaries c2009/12/10 v803 a 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. 1 aJordan, Stephen, P.1 aWocjan, Pawel uhttp://arxiv.org/abs/0904.2211v201422nas a2200145 4500008004100000245005900041210005900100260001500159520097700174100002201151700002401173700001801197700002401215856003701239 2009 eng d00aEfficient quantum processing of ideals in finite rings0 aEfficient quantum processing of ideals in finite rings c2009/07/313 a 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. 1 aWocjan, Pawel, M.1 aJordan, Stephen, P.1 aAhmadi, Hamed1 aBrennan, Joseph, P. uhttp://arxiv.org/abs/0908.0022v101125nas a2200145 4500008004100000245006500041210006500106260001500171300001200186490000600198520068700204100002400891700001800915856004600933 2009 eng d00aEstimating Jones and HOMFLY polynomials with One Clean Qubit0 aEstimating Jones and HOMFLY polynomials with One Clean Qubit c2009/03/01 a264-2890 v93 a

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.

1 aJordan, Stephen, P.1 aWocjan, Pawel uhttp://dl.acm.org/citation.cfm?id=201178701463nas a2200145 4500008004100000245007500041210006900116260001500185300001200200490000600212520100100218100002001219700002401239856005401263 2008 eng d00aEstimating Jones polynomials is a complete problem for one clean qubit0 aEstimating Jones polynomials is a complete problem for one clean c2008/09/01 a681-7140 v83 a

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.

1 aShor, Peter, W.1 aJordan, Stephen, P. uhttp://dl.acm.org/citation.cfm?id=2017011.201701201345nas a2200109 4500008004100000245009200041210006900133260001500202520095700217100002401174856003701198 2008 eng d00aFast quantum algorithms for approximating some irreducible representations of groups 0 aFast quantum algorithms for approximating some irreducible repre c2008/11/043 a 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. 1 aJordan, Stephen, P. uhttp://arxiv.org/abs/0811.0562v201152nas a2200133 4500008004100000245004500041210004500086260001400131490000700145520078700152100002400939700001800963856003700981 2008 eng d00aPerturbative Gadgets at Arbitrary Orders0 aPerturbative Gadgets at Arbitrary Orders c2008/6/190 v773 a 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. 1 aJordan, Stephen, P.1 aFarhi, Edward uhttp://arxiv.org/abs/0802.1874v401766nas a2200181 4500008004100000245008100041210006900122260001500191300001800206490000800224520121000232100001701442700002401459700002001483700002001503700002401523856003701547 2008 eng d00aPolynomial-time quantum algorithm for the simulation of chemical dynamics 0 aPolynomialtime quantum algorithm for the simulation of chemical  c2008/11/24 a18681 - 186860 v1053 a 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. 1 aKassal, Ivan1 aJordan, Stephen, P.1 aLove, Peter, J.1 aMohseni, Masoud1 aAspuru-Guzik, Alán uhttp://arxiv.org/abs/0801.2986v301534nas a2200109 4500008004100000245004900041210004900090260001500139520120900154100002401363856003701387 2008 eng d00aQuantum Computation Beyond the Circuit Model0 aQuantum Computation Beyond the Circuit Model c2008/09/133 a 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. 1 aJordan, Stephen, P. uhttp://arxiv.org/abs/0809.2307v101177nas a2200145 4500008004100000245006100041210006100102260001500163490000700178520074000185100002400925700001800949700002000967856004400987 2006 eng d00aError correcting codes for adiabatic quantum computation0 aError correcting codes for adiabatic quantum computation c2006/11/140 v743 a 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. 1 aJordan, Stephen, P.1 aFarhi, Edward1 aShor, Peter, W. uhttp://arxiv.org/abs/quant-ph/0512170v300806nas a2200121 4500008004100000245006100041210006100102260001400163490000700177520043200184100002400616856004400640 2005 eng d00aFast quantum algorithm for numerical gradient estimation0 aFast quantum algorithm for numerical gradient estimation c2005/7/280 v953 a 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. 1 aJordan, Stephen, P. uhttp://arxiv.org/abs/quant-ph/0405146v2