While there has been extensive previous work on efficient quantum algorithms for linear differential equations, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. Despite this obstacle, we develop a quantum algorithm for initial value problems described by dissipative quadratic n-dimensional ordinary differential equations. Assuming R<1, where R is a parameter characterizing the ratio of the nonlinearity to the linear dissipation, this algorithm has complexity T2poly(logT,logn)/ϵ, where T is the evolution time and ϵ is the allowed error in the output quantum state. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. We achieve this improvement using the method of Carleman linearization, for which we give an improved convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for R≥2–√. Finally, we discuss potential applications of this approach to problems arising in biology as well as in fluid and plasma dynamics.

VL - 118 UR - https://arxiv.org/abs/2011.03185 U5 - https://doi.org/10.1073/pnas.2026805118 ER - TY - JOUR T1 - Quantum exploration algorithms for multi-armed bandits JF - Proceedings of the 35th Conference on Artificial Intelligence (AAAI 2021) Y1 - 2021 A1 - Daochen Wang A1 - Xuchen You A1 - Tongyang Li A1 - Andrew M. Childs AB -Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we show that we can find the best arm with fixed confidence using O~(∑ni=2Δ−2i−−−−−−−−√) quantum queries, where Δi represents the difference between the mean reward of the best arm and the ith-best arm. This algorithm, based on variable-time amplitude amplification and estimation, gives a quadratic speedup compared to the best possible classical result. We also prove a matching quantum lower bound (up to poly-logarithmic factors).

VL - 35 U4 - 10102-10110 UR - https://ojs.aaai.org/index.php/AAAI/article/view/17212 CP - 11 ER - TY - JOUR T1 - Quantum routing with fast reversals JF - Quantum Y1 - 2021 A1 - Aniruddha Bapat A1 - Andrew M. Childs A1 - Alexey V. Gorshkov A1 - Samuel King A1 - Eddie Schoute A1 - Hrishee Shastri AB -We present methods for implementing arbitrary permutations of qubits under interaction constraints. Our protocols make use of previous methods for rapidly reversing the order of qubits along a path. Given nearest-neighbor interactions on a path of length n, we show that there exists a constant ϵ≈0.034 such that the quantum routing time is at most (1−ϵ)n, whereas any swap-based protocol needs at least time n−1. This represents the first known quantum advantage over swap-based routing methods and also gives improved quantum routing times for realistic architectures such as grids. Furthermore, we show that our algorithm approaches a quantum routing time of 2n/3 in expectation for uniformly random permutations, whereas swap-based protocols require time n asymptotically. Additionally, we consider sparse permutations that route k≤n qubits and give algorithms with quantum routing time at most n/3+O(k2) on paths and at most 2r/3+O(k2) on general graphs with radius r.

VL - 5 UR - https://arxiv.org/abs/2103.03264 U5 - https://doi.org/10.22331/q-2021-08-31-533 ER - TY - JOUR T1 - Theory of Trotter Error with Commutator Scaling JF - Phys. Rev. X Y1 - 2021 A1 - Andrew M. Childs A1 - Yuan Su A1 - Minh C. Tran A1 - Nathan Wiebe A1 - Shuchen Zhu AB -The Lie-Trotter formula, together with its higher-order generalizations, provides a direct approach to decomposing the exponential of a sum of operators. Despite significant effort, the error scaling of such product formulas remains poorly understood. We develop a theory of Trotter error that overcomes the limitations of prior approaches based on truncating the Baker-Campbell-Hausdorff expansion. Our analysis directly exploits the commutativity of operator summands, producing tighter error bounds for both real- and imaginary-time evolutions. Whereas previous work achieves similar goals for systems with geometric locality or Lie-algebraic structure, our approach holds in general. We give a host of improved algorithms for digital quantum simulation and quantum Monte Carlo methods, including simulations of second-quantized plane-wave electronic structure, k-local Hamiltonians, rapidly decaying power-law interactions, clustered Hamiltonians, the transverse field Ising model, and quantum ferromagnets, nearly matching or even outperforming the best previous results. We obtain further speedups using the fact that product formulas can preserve the locality of the simulated system. Specifically, we show that local observables can be simulated with complexity independent of the system size for power-law interacting systems, which implies a Lieb-Robinson bound as a byproduct. Our analysis reproduces known tight bounds for first- and second-order formulas. Our higher-order bound overestimates the complexity of simulating a one-dimensional Heisenberg model with an even-odd ordering of terms by only a factor of 5, and is close to tight for power-law interactions and other orderings of terms. This suggests that our theory can accurately characterize Trotter error in terms of both asymptotic scaling and constant prefactor.

VL - 11 U4 - 49 UR - https://arxiv.org/abs/1912.08854 CP - 1 U5 - https://journals.aps.org/prx/abstract/10.1103/PhysRevX.11.011020 ER - TY - JOUR T1 - Can graph properties have exponential quantum speedup? Y1 - 2020 A1 - Andrew M. Childs A1 - Daochen Wang AB -Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity R of any graph property P has R(P)=O(Q(P)6), where Q is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove R(P)=O(Q(P)3l) for any l-uniform hypergraph property P in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.

UR - https://arxiv.org/abs/2001.10520 ER - TY - JOUR T1 - Destructive Error Interference in Product-Formula Lattice Simulation JF - Phys. Rev. Lett. Y1 - 2020 A1 - Minh C. Tran A1 - Su-Kuan Chu A1 - Yuan Su A1 - Andrew M. Childs A1 - Alexey V. Gorshkov AB -Quantum computers can efficiently simulate the dynamics of quantum systems. In this paper, we study the cost of digitally simulating the dynamics of several physically relevant systems using the first-order product formula algorithm. We show that the errors from different Trotterization steps in the algorithm can interfere destructively, yielding a much smaller error than previously estimated. In particular, we prove that the total error in simulating a nearest-neighbor interacting system of n sites for time t using the first-order product formula with r time slices is O(nt/r+nt3/r2) when nt2/r is less than a small constant. Given an error tolerance ε, the error bound yields an estimate of max{O(n2t/ε),O(n2t3/2/ε1/2)} for the total gate count of the simulation. The estimate is tighter than previous bounds and matches the empirical performance observed in Childs et al. [PNAS 115, 9456-9461 (2018)]. We also provide numerical evidence for potential improvements and conjecture an even tighter estimate for the gate count.

VL - 124 UR - https://arxiv.org/abs/1912.11047 CP - 220502 U5 - https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.124.220502 ER - TY - JOUR T1 - High-precision quantum algorithms for partial differential equations JF - Accepted for Publication in Quantum Y1 - 2020 A1 - Andrew M. Childs A1 - Jin-Peng Liu A1 - Aaron Ostrander AB -Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity poly(1/ε), where ε is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be poly(d,log(1/ε)), where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.

UR - https://arxiv.org/abs/2002.07868 ER - TY - JOUR T1 - Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions Y1 - 2020 A1 - Andrew Y. Guo A1 - Abhinav Deshpande A1 - Su-Kuan Chu A1 - Zachary Eldredge A1 - Przemyslaw Bienias A1 - Dhruv Devulapalli A1 - Yuan Su A1 - Andrew M. Childs A1 - Alexey V. Gorshkov AB -The standard circuit model for quantum computation presumes the ability to directly perform gates between arbitrary pairs of qubits, which is unlikely to be practical for large-scale experiments. Power-law interactions with strength decaying as 1/rα in the distance r provide an experimentally realizable resource for information processing, whilst still retaining long-range connectivity. We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets. Our implementation allows the quantum Fourier transform (QFT) and Shor's algorithm to be performed on a D-dimensional lattice in time logarithmic in the number of qubits for interactions with α≤D. As a corollary, we show that power-law systems with α≤D are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable. Complementarily, we develop a new technique to give a general lower bound, linear in the size of the system, on the time required to implement the QFT and the fanout gate in systems that are constrained by a linear light cone. This allows us to prove an asymptotically tighter lower bound for long-range systems than is possible with previously available techniques.

UR - https://arxiv.org/abs/2007.00662 ER - TY - JOUR T1 - Nearly optimal time-independent reversal of a spin chain JF - accepted for publication in Physical Review Research Y1 - 2020 A1 - Aniruddha Bapat A1 - Eddie Schoute A1 - Alexey V. Gorshkov A1 - Andrew M. Childs AB -We propose a time-independent Hamiltonian protocol for the reversal of qubit ordering in a chain of N spins. Our protocol has an easily implementable nearest-neighbor, transverse-field Ising model Hamiltonian with time-independent, non-uniform couplings. Under appropriate normalization, we implement this state reversal three times faster than a naive approach using SWAP gates, in time comparable to a protocol of Raussendorf [Phys. Rev. A 72, 052301 (2005)] that requires dynamical control. We also prove lower bounds on state reversal by using results on the entanglement capacity of Hamiltonians and show that we are within a factor 1.502(1+1/N) of the shortest time possible. Our lower bound holds for all nearest-neighbor qubit protocols with arbitrary finite ancilla spaces and local operations and classical communication. Finally, we extend our protocol to an infinite family of nearest-neighbor, time-independent Hamiltonian protocols for state reversal. This includes chains with nearly uniform coupling that may be especially feasible for experimental implementation.

UR - https://arxiv.org/abs/2003.02843 ER - TY - JOUR T1 - Non-interactive classical verification of quantum computation JF - Theory of Cryptography Conference (TCC) Y1 - 2020 A1 - Gorjan Alagic A1 - Andrew M. Childs A1 - Alex B. Grilo A1 - Shih-Han Hung AB -In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In this work, we show that this same task can in fact be performed non-interactively and in zero-knowledge.

Our protocols result from a sequence of significant improvements to the original four-message protocol of Mahadev. We begin by making the first message instance-independent and moving it to an offline setup phase. We then establish a parallel repetition theorem for the resulting three-message protocol, with an asymptotically optimal rate. This, in turn, enables an application of the Fiat-Shamir heuristic, eliminating the second message and giving a non-interactive protocol. Finally, we employ classical non-interactive zero-knowledge (NIZK) arguments and classical fully homomorphic encryption (FHE) to give a zero-knowledge variant of this construction. This yields the first purely classical NIZK argument system for QMA, a quantum analogue of NP.

We establish the security of our protocols under standard assumptions in quantum-secure cryptography. Specifically, our protocols are secure in the Quantum Random Oracle Model, under the assumption that Learning with Errors is quantumly hard. The NIZK construction also requires circuit-private FHE.

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n-dimensional convex body using O~(n) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω~(n−−√) evaluation queries and Ω(n−−√) membership queries.

VL - 4 UR - https://arxiv.org/abs/1809.01731 CP - 221 U5 - https://doi.org/10.22331/q-2020-01-13-221 ER - TY - JOUR T1 - Quantum Coupon Collector JF - Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics Y1 - 2020 A1 - Srinivasan Arunachalam A1 - Aleksandrs Belovs A1 - Andrew M. Childs A1 - Robin Kothari A1 - Ansis Rosmanis A1 - Ronald de Wolf AB -We study how efficiently a k-element set S⊆[n] can be learned from a uniform superposition |S⟩ of its elements. One can think of |S⟩=∑i∈S|i⟩/|S|−−−√ as the quantum version of a uniformly random sample over S, as in the classical analysis of the ``coupon collector problem.'' We show that if k is close to n, then we can learn S using asymptotically fewer quantum samples than random samples. In particular, if there are n−k=O(1) missing elements then O(k) copies of |S⟩ suffice, in contrast to the Θ(klogk) random samples needed by a classical coupon collector. On the other hand, if n−k=Ω(k), then Ω(klogk) quantum samples are~necessary. More generally, we give tight bounds on the number of quantum samples needed for every k and n, and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through |S⟩. Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.

VL - 158 U4 - 10:1-10:17 UR - https://arxiv.org/abs/2002.07688 U5 - 10.4230/LIPIcs.TQC.2020.10 ER - TY - JOUR T1 - Quantum spectral methods for differential equations JF - Commun. Math. Phys. Y1 - 2020 A1 - Andrew M. Childs A1 - Jin-Peng Liu AB -Recently developed quantum algorithms address computational challenges in numerical analysis by performing linear algebra in Hilbert space. Such algorithms can produce a quantum state proportional to the solution of a d-dimensional system of linear equations or linear differential equations with complexity poly(logd). While several of these algorithms approximate the solution to within ε with complexity poly(log(1/ε)), no such algorithm was previously known for differential equations with time-dependent coefficients. Here we develop a quantum algorithm for linear ordinary differential equations based on so-called spectral methods, an alternative to finite difference methods that approximates the solution globally. Using this approach, we give a quantum algorithm for time-dependent initial and boundary value problems with complexity poly(logd,log(1/ε)).

VL - 375 U4 - 1427-1457 UR - https://arxiv.org/abs/1901.00961 U5 - https://doi.org/10.1007/s00220-020-03699-z ER - TY - JOUR T1 - Signaling and Scrambling with Strongly Long-Range Interactions JF - Physical Review A Y1 - 2020 A1 - Andrew Y. Guo A1 - Minh C. Tran A1 - Andrew M. Childs A1 - Alexey V. Gorshkov A1 - Zhe-Xuan Gong AB -Strongly long-range interacting quantum systems---those with interactions decaying as a power-law 1/rα in the distance r on a D-dimensional lattice for α≤D---have received significant interest in recent years. They are present in leading experimental platforms for quantum computation and simulation, as well as in theoretical models of quantum information scrambling and fast entanglement creation. Since no notion of locality is expected in such systems, a general understanding of their dynamics is lacking. As a first step towards rectifying this problem, we prove two new Lieb-Robinson-type bounds that constrain the time for signaling and scrambling in strongly long-range interacting systems, for which no tight bounds were previously known. Our first bound applies to systems mappable to free-particle Hamiltonians with long-range hopping, and is saturable for α≤D/2. Our second bound pertains to generic long-range interacting spin Hamiltonians, and leads to a tight lower bound for the signaling time to extensive subsets of the system for all α<D. This result also lower-bounds the scrambling time, and suggests a path towards achieving a tight scrambling bound that can prove the long-standing fast scrambling conjecture.

VL - 102 UR - https://arxiv.org/abs/1906.02662 CP - 010401(R) U5 - https://journals.aps.org/pra/abstract/10.1103/PhysRevA.102.010401 ER - TY - CONF T1 - Symmetries, graph properties, and quantum speedups T2 - Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649–660 (2020) Y1 - 2020 A1 - Shalev Ben-David A1 - Andrew M. Childs A1 - Andras Gilyen A1 - William Kretschmer A1 - Supartha Podder A1 - Daochen Wang AB -Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup?

In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups.

In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).

The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For the case of sparse Hamiltonian simulation, the gate complexity scales with the L1 norm ∫t0dτ∥H(τ)∥max, whereas the best previous results scale with tmaxτ∈[0,t]∥H(τ)∥max. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. By leveraging the L1-norm information, we obtain polynomial speedups for semi-classical simulations of scattering processes in quantum chemistry.

VL - 4 UR - https://arxiv.org/abs/1906.07115 CP - 254 U5 - https://doi.org/10.22331/q-2020-04-20-254 ER - TY - JOUR T1 - Circuit Transformations for Quantum Architectures JF - Proceedings of TQC 2019, LIPIcs Y1 - 2019 A1 - Andrew M. Childs A1 - Eddie Schoute A1 - Cem M. Unsal AB -Quantum computer architectures impose restrictions on qubit interactions. We propose efficient circuit transformations that modify a given quantum circuit to fit an architecture, allowing for any initial and final mapping of circuit qubits to architecture qubits. To achieve this, we first consider the qubit movement subproblem and use the routing via matchings framework to prove tighter bounds on parallel routing. In practice, we only need to perform partial permutations, so we generalize routing via matchings to that setting. We give new routing procedures for common architecture graphs and for the generalized hierarchical product of graphs, which produces subgraphs of the Cartesian product. Secondly, for serial routing, we consider the token swapping framework and extend a 4-approximation algorithm for general graphs to support partial permutations. We apply these routing procedures to give several circuit transformations, using various heuristic qubit placement subroutines. We implement these transformations in software and compare their performance for large quantum circuits on grid and modular architectures, identifying strategies that work well in practice.

VL - 135 UR - https://arxiv.org/abs/1902.09102 CP - 3 U5 - https://doi.org/10.4230/LIPIcs.TQC.2019.3 ER - TY - JOUR T1 - Faster quantum simulation by randomization JF - Quantum Y1 - 2019 A1 - Andrew M. Childs A1 - Aaron Ostrander A1 - Yuan Su AB -Product formulas can be used to simulate Hamiltonian dynamics on a quantum computer by approximating the exponential of a sum of operators by a product of exponentials of the individual summands. This approach is both straightforward and surprisingly efficient. We show that by simply randomizing how the summands are ordered, one can prove stronger bounds on the quality of approximation and thereby give more efficient simulations. Indeed, we show that these bounds can be asymptotically better than previous bounds that exploit commutation between the summands, despite using much less information about the structure of the Hamiltonian. Numerical evidence suggests that our randomized algorithm may be advantageous even for near-term quantum simulation.

VL - 3 UR - https://arxiv.org/abs/1805.08385 CP - 182 U5 - https://doi.org/10.22331/q-2019-09-02-182 ER - TY - JOUR T1 - Locality and digital quantum simulation of power-law interactions JF - Phys. Rev. X 9, 031006 Y1 - 2019 A1 - Minh C. Tran A1 - Andrew Y. Guo A1 - Yuan Su A1 - James R. Garrison A1 - Zachary Eldredge A1 - Michael Foss-Feig A1 - Andrew M. Childs A1 - Alexey V. Gorshkov AB -The propagation of information in non-relativistic quantum systems obeys a speed limit known as a Lieb-Robinson bound. We derive a new Lieb-Robinson bound for systems with interactions that decay with distance r as a power law, 1/rα. The bound implies an effective light cone tighter than all previous bounds. Our approach is based on a technique for approximating the time evolution of a system, which was first introduced as part of a quantum simulation algorithm by Haah et al. [arXiv:1801.03922]. To bound the error of the approximation, we use a known Lieb-Robinson bound that is weaker than the bound we establish. This result brings the analysis full circle, suggesting a deep connection between Lieb-Robinson bounds and digital quantum simulation. In addition to the new Lieb-Robinson bound, our analysis also gives an error bound for the Haah et al. quantum simulation algorithm when used to simulate power-law decaying interactions. In particular, we show that the gate count of the algorithm scales with the system size better than existing algorithms when α>3D (where D is the number of dimensions).

VL - 9 UR - https://arxiv.org/abs/1808.05225 CP - 031006 U5 - https://doi.org/10.1103/PhysRevX.9.031006 ER - TY - JOUR T1 - Nearly optimal lattice simulation by product formulas JF - Phys. Rev. Lett. Y1 - 2019 A1 - Andrew M. Childs A1 - Yuan Su AB -Product formulas provide a straightforward yet surprisingly efficient approach to quantum simulation. We show that this algorithm can simulate an n-qubit Hamiltonian with nearest-neighbor interactions evolving for time t using only (nt)1+o(1) gates. While it is reasonable to expect this complexity---in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill---we are not aware of a straightforward proof. Our approach is based on an analysis of the local error structure of product formulas, as introduced by Descombes and Thalhammer and significantly simplified here. We prove error bounds for canonical product formulas, which include well-known constructions such as the Lie-Trotter-Suzuki formulas. We also develop a local error representation for time-dependent Hamiltonian simulation, and we discuss generalizations to periodic boundary conditions, constant-range interactions, and higher dimensions. Combined with a previous lower bound, our result implies that product formulas can simulate lattice Hamiltonians with nearly optimal gate complexity.

VL - 123 UR - https://arxiv.org/abs/1901.00564 CP - 050503 U5 - https://doi.org/10.1103/PhysRevLett.123.050503 ER - TY - JOUR T1 - Quantum algorithm for estimating volumes of convex bodies Y1 - 2019 A1 - Shouvanik Chakrabarti A1 - Andrew M. Childs A1 - Shih-Han Hung A1 - Tongyang Li A1 - Chunhao Wang A1 - Xiaodi Wu AB -Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an n-dimensional convex body within multiplicative error ε using O~(n3.5+n2.5/ε) queries to a membership oracle and O~(n5.5+n4.5/ε) additional arithmetic operations. For comparison, the best known classical algorithm uses O~(n4+n3/ε2) queries and O~(n6+n5/ε2) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of "Chebyshev cooling", where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error.

UR - https://arxiv.org/abs/1908.03903 ER - TY - JOUR T1 - Automated optimization of large quantum circuits with continuous parameters JF - npj:Quantum Information Y1 - 2018 A1 - Yunseong Nam A1 - Neil J. Ross A1 - Yuan Su A1 - Andrew M. Childs A1 - Dmitri Maslov AB -We develop and implement automated methods for optimizing quantum circuits of the size and type expected in quantum computations that outperform classical computers. We show how to handle continuous gate parameters and report a collection of fast algorithms capable of optimizing large-scale quantum circuits. For the suite of benchmarks considered, we obtain substantial reductions in gate counts. In particular, we provide better optimization in significantly less time than previous approaches, while making minimal structural changes so as to preserve the basic layout of the underlying quantum algorithms. Our results help bridge the gap between the computations that can be run on existing hardware and those that are expected to outperform classical computers.

VL - 4 UR - https://arxiv.org/abs/1710.07345 CP - 23 U5 - https://doi.org/10.1038/s41534-018-0072-4 ER - TY - JOUR T1 - Quantum algorithm for multivariate polynomial interpolation JF - Proceedings of The Royal Society A Y1 - 2018 A1 - Jianxin Chen A1 - Andrew M. Childs A1 - Shih-Han Hung AB -How many quantum queries are required to determine the coefficients of a degree-d polynomial in n variables? We present and analyze quantum algorithms for this multivariate polynomial interpolation problem over the fields Fq, R, and C. We show that kC and 2kC queries suffice to achieve probability 1 for C and R, respectively, where kC = ⌈ 1 n+1 ( n+d d )⌉ except for d = 2 and four other special cases. For Fq, we show that ⌈ d n+d ( n+d d )⌉ queries suffice to achieve probability approaching 1 for large field order q. The classical query complexity of this problem is ( n+d d ), so our result provides a speedup by a factor of n + 1, n+1 2 , and n+d d for C, R, and Fq, respectively. Thus we find a much larger gap between classical and quantum algorithms than the univariate case, where the speedup is by a factor of 2. For the case of Fq, we conjecture that 2kC queries also suffice to achieve probability approaching 1 for large field order q, although we leave this as an open problem.

VL - 474 UR - http://rspa.royalsocietypublishing.org/content/474/2209/20170480 CP - 2209 U5 - 10.1098/rspa.2017.0480 ER - TY - JOUR T1 - Toward the first quantum simulation with quantum speedup JF - Proceedings of the National Academy of Sciences Y1 - 2018 A1 - Andrew M. Childs A1 - Dmitri Maslov A1 - Yunseong Nam A1 - Neil J. Ross A1 - Yuan Su AB -With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.

VL - 115 U4 - 9456-9461 UR - https://arxiv.org/abs/1711.10980 U5 - https://doi.org/10.1073/pnas.1801723115 ER - TY - JOUR T1 - Efficient simulation of sparse Markovian quantum dynamics JF - Quantum Information and Computation Y1 - 2017 A1 - Andrew M. Childs A1 - Tongyang Li AB -Quantum algorithms for simulating Hamiltonian dynamics have been extensively developed, but there has been much less work on quantum algorithms for simulating the dynamics of open quantum systems. We give the first efficient quantum algorithms for simulating Markovian quantum dynamics generated by Lindbladians that are not necessarily local. We introduce two approaches to simulating sparse Lindbladians. First, we show how to simulate Lindbladians that act within small invariant subspaces using a quantum algorithm to implement sparse Stinespring isometries. Second, we develop a method for simulating sparse Lindblad operators by concatenating a sequence of short-time evolutions. We also show limitations on Lindbladian simulation by proving a no-fast-forwarding theorem for simulating sparse Lindbladians in a black-box model.

VL - 17 U4 - 901-947 UR - https://arxiv.org/abs/1611.05543 U5 - 10.26421/QIC17.11-12 ER - TY - JOUR T1 - Quantum algorithm for linear differential equations with exponentially improved dependence on precision JF - Communications in Mathematical Physics Y1 - 2017 A1 - Dominic W. Berry A1 - Andrew M. Childs A1 - Aaron Ostrander A1 - Guoming Wang AB -We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.

VL - 356 U4 - 1057-1081 UR - https://arxiv.org/abs/1701.03684 CP - 3 ER - TY - JOUR T1 - Quantum algorithm for systems of linear equations with exponentially improved dependence on precision JF - SIAM Journal on Computing Y1 - 2017 A1 - Andrew M. Childs A1 - Robin Kothari A1 - Rolando D. Somma AB -Harrow, Hassidim, and Lloyd showed that for a suitably specified N×N matrix A and N-dimensional vector b⃗ , there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax⃗ =b⃗ . If A is sparse and well-conditioned, their algorithm runs in time poly(logN,1/ϵ), where ϵ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(1/ϵ), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on ϵ is prohibitive.

VL - 46 U4 - 1920-1950 UR - http://epubs.siam.org/doi/10.1137/16M1087072 CP - 6 U5 - 10.1137/16M1087072 ER - TY - JOUR T1 - Complexity of the XY antiferromagnet at fixed magnetization JF - Quantum Information and Computation Y1 - 2016 A1 - Andrew M. Childs A1 - David Gosset A1 - Zak Webb AB - We prove that approximating the ground energy of the antiferromagnetic XY model on a simple graph at fixed magnetization (given as part of the instance specification) is QMA-complete. To show this, we strengthen a previous result by establishing QMA-completeness for approximating the ground energy of the Bose-Hubbard model on simple graphs. Using a connection between the XY and Bose-Hubbard models that we exploited in previous work, this establishes QMA-completeness of the XY model. VL - 16 U4 - 1-18 UR - http://arxiv.org/abs/1503.07083v1 CP - 1-2 ER - TY - JOUR T1 - Optimal quantum algorithm for polynomial interpolation JF - 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) Y1 - 2016 A1 - Andrew M. Childs A1 - Wim van Dam A1 - Shih-Han Hung A1 - Igor E. Shparlinski AB -We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability.

VL - 55 U4 - 16:1--16:13 SN - 978-3-95977-013-2 UR - http://arxiv.org/abs/1509.09271 U5 - http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.16 ER - TY - JOUR T1 - Optimal state discrimination and unstructured search in nonlinear quantum mechanics JF - Physical Review A Y1 - 2016 A1 - Andrew M. Childs A1 - Joshua Young AB - Nonlinear variants of quantum mechanics can solve tasks that are impossible in standard quantum theory, such as perfectly distinguishing nonorthogonal states. Here we derive the optimal protocol for distinguishing two states of a qubit using the Gross-Pitaevskii equation, a model of nonlinear quantum mechanics that arises as an effective description of Bose-Einstein condensates. Using this protocol, we present an algorithm for unstructured search in the Gross-Pitaevskii model, obtaining an exponential improvement over a previous algorithm of Meyer and Wong. This result establishes a limitation on the effectiveness of the Gross-Pitaevskii approximation. More generally, we demonstrate similar behavior under a family of related nonlinearities, giving evidence that the ability to quickly discriminate nonorthogonal states and thereby solve unstructured search is a generic feature of nonlinear quantum mechanics. VL - 93 U4 - 022314 UR - http://arxiv.org/abs/1507.06334 CP - 2 U5 - 10.1103/PhysRevA.93.022314 ER - TY - JOUR T1 - Hamiltonian simulation with nearly optimal dependence on all parameters JF - Proceedings of the 56th IEEE Symposium on Foundations of Computer Science Y1 - 2015 A1 - Dominic W. Berry A1 - Andrew M. Childs A1 - Robin Kothari AB - We present an algorithm for sparse Hamiltonian simulation that has optimal dependence on all parameters of interest (up to log factors). Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity $d$ at the expense of poor scaling in the allowed error $\epsilon$. In contrast, an approach based on fractional-query simulation provides optimal scaling in $\epsilon$ at the expense of poor scaling in $d$. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm achieves near-linear scaling in $\tau := d \|H\|_{\max} t$ and sublogarithmic scaling in $1/\epsilon$. Our dependence on $\epsilon$ is optimal, and we prove a new lower bound showing that no algorithm can have sublinear dependence on $\tau$. U4 - 792-809 UR - http://arxiv.org/abs/1501.01715 U5 - 10.1109/FOCS.2015.54 ER - TY - JOUR T1 - Momentum switches JF - Quantum Information and Computation Y1 - 2015 A1 - Andrew M. Childs A1 - David Gosset A1 - Daniel Nagaj A1 - Mouktik Raha A1 - Zak Webb AB - Certain continuous-time quantum walks can be viewed as scattering processes. These processes can perform quantum computations, but it is challenging to design graphs with desired scattering behavior. In this paper, we study and construct momentum switches, graphs that route particles depending on their momenta. We also give an example where there is no exact momentum switch, although we construct an arbitrarily good approximation. VL - 15 U4 - 601-621 UR - http://arxiv.org/abs/1406.4510v1 CP - 7-8 J1 - Quantum Information and Computation 15 ER - TY - JOUR T1 - Simulating Hamiltonian dynamics with a truncated Taylor series JF - Physical Review Letters Y1 - 2015 A1 - Dominic W. Berry A1 - Andrew M. Childs A1 - Richard Cleve A1 - Robin Kothari A1 - Rolando D. Somma AB - We describe a simple, efficient method for simulating Hamiltonian dynamics on a quantum computer by approximating the truncated Taylor series of the evolution operator. Our method can simulate the time evolution of a wide variety of physical systems. As in another recent algorithm, the cost of our method depends only logarithmically on the inverse of the desired precision, which is optimal. However, we simplify the algorithm and its analysis by using a method for implementing linear combinations of unitary operations to directly apply the truncated Taylor series. VL - 114 U4 - 090502 UR - http://arxiv.org/abs/1412.4687v1 CP - 9 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.114.090502 ER - TY - JOUR T1 - The Bose-Hubbard model is QMA-complete JF - Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014) Y1 - 2014 A1 - Andrew M. Childs A1 - David Gosset A1 - Zak Webb AB - The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients. VL - 8572 U4 - 308-319 UR - http://arxiv.org/abs/1311.3297v1 J1 - Proceedings of the 41st International Colloquium on Automata U5 - 10.1007/978-3-662-43948-7_26 ER - TY - JOUR T1 - The computational power of matchgates and the XY interaction on arbitrary graphs JF - Quantum Information and Computation Y1 - 2014 A1 - Daniel J. Brod A1 - Andrew M. Childs AB - Matchgates are a restricted set of two-qubit gates known to be classically simulable when acting on nearest-neighbor qubits on a path, but universal for quantum computation when the qubits are arranged on certain other graphs. Here we characterize the power of matchgates acting on arbitrary graphs. Specifically, we show that they are universal on any connected graph other than a path or a cycle, and that they are classically simulable on a cycle. We also prove the same dichotomy for the XY interaction, a proper subset of matchgates related to some implementations of quantum computing. VL - 14 U4 - 901-916 UR - http://arxiv.org/abs/1308.1463v1 CP - 11-12 J1 - Quantum Information and Computation 14 ER - TY - JOUR T1 - Constructing elliptic curve isogenies in quantum subexponential time JF - Journal of Mathematical Cryptology Y1 - 2014 A1 - Andrew M. Childs A1 - David Jao A1 - Vladimir Soukharev AB - Given two elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit an isogeny between them, but finding such an isogeny is believed to be computationally difficult. The fastest known classical algorithm takes exponential time, and prior to our work no faster quantum algorithm was known. Recently, public-key cryptosystems based on the presumed hardness of this problem have been proposed as candidates for post-quantum cryptography. In this paper, we give a subexponential-time quantum algorithm for constructing isogenies, assuming the Generalized Riemann Hypothesis (but with no other assumptions). Our algorithm is based on a reduction to a hidden shift problem, together with a new subexponential-time algorithm for evaluating isogenies from kernel ideals (under only GRH), and represents the first nontrivial application of Kuperberg's quantum algorithm for the hidden shift problem. This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream quantum-resistant cryptosystems such as lattice-based cryptosystems. VL - 8 U4 - 1 - 29 UR - http://arxiv.org/abs/1012.4019v2 CP - 1 J1 - J. Math. Cryptol. U5 - 10.1515/jmc-2012-0016 ER - TY - JOUR T1 - Exponential improvement in precision for simulating sparse Hamiltonians JF - Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014) Y1 - 2014 A1 - Dominic W. Berry A1 - Andrew M. Childs A1 - Richard Cleve A1 - Robin Kothari A1 - Rolando D. Somma AB - We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$-sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$ with precision $\epsilon$ using $O\big(\tau \frac{\log(\tau/\epsilon)}{\log\log(\tau/\epsilon)}\big)$ queries and $O\big(\tau \frac{\log^2(\tau/\epsilon)}{\log\log(\tau/\epsilon)}n\big)$ additional 2-qubit gates, where $\tau = d^2 \|{H}\|_{\max} t$. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error. U4 - 283-292 SN - 978-1-4503-2710-7 UR - http://arxiv.org/abs/1312.1414v2 J1 - Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014) U5 - 10.1145/2591796.2591854 ER - TY - JOUR T1 - Quantum computation of discrete logarithms in semigroups JF - Journal of Mathematical Cryptology Y1 - 2014 A1 - Andrew M. Childs A1 - Gábor Ivanyos AB - We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and discrete log as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete log problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete log problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to $k \ge 2$ generators in a black-box abelian semigroup of order $N$ requires $\tilde \Theta(N^{\frac{1}{2}-\frac{1}{2k}})$ quantum queries. VL - 8 UR - http://arxiv.org/abs/1310.6238v2 CP - 4 J1 - Journal of Mathematical Cryptology 8 U5 - 10.1515/jmc-2013-0038 ER - TY - JOUR T1 - Spatial search by continuous-time quantum walks on crystal lattices JF - Physical Review A Y1 - 2014 A1 - Andrew M. Childs A1 - Yimin Ge AB - We consider the problem of searching a general $d$-dimensional lattice of $N$ vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behaviour near a Dirac point, we develop algorithms that solve the problem in a time of $O(\sqrt N)$ for $d>2$ and $O(\sqrt N \log N)$ in $d=2$. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory. VL - 89 UR - http://arxiv.org/abs/1403.2676v2 CP - 5 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.89.052337 ER - TY - JOUR T1 - Easy and hard functions for the Boolean hidden shift problem JF - Proceedings of TQC 2013 Y1 - 2013 A1 - Andrew M. Childs A1 - Robin Kothari A1 - Maris Ozols A1 - Martin Roetteler AB - We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem. VL - 22 U4 - 50-79 UR - http://arxiv.org/abs/1304.4642v1 J1 - Proceedings of TQC 2013 U5 - 10.4230/LIPIcs.TQC.2013.50 ER - TY - JOUR T1 - A framework for bounding nonlocality of state discrimination JF - Communications in Mathematical Physics Y1 - 2013 A1 - Andrew M. Childs A1 - Debbie Leung A1 - Laura Mancinska A1 - Maris Ozols AB - We consider the class of protocols that can be implemented by local quantum operations and classical communication (LOCC) between two parties. In particular, we focus on the task of discriminating a known set of quantum states by LOCC. Building on the work in the paper "Quantum nonlocality without entanglement" [BDF+99], we provide a framework for bounding the amount of nonlocality in a given set of bipartite quantum states in terms of a lower bound on the probability of error in any LOCC discrimination protocol. We apply our framework to an orthonormal product basis known as the domino states and obtain an alternative and simplified proof that quantifies its nonlocality. We generalize this result for similar bases in larger dimensions, as well as the "rotated" domino states, resolving a long-standing open question [BDF+99]. VL - 323 U4 - 1121 - 1153 UR - http://arxiv.org/abs/1206.5822v1 CP - 3 J1 - Commun. Math. Phys. U5 - 10.1007/s00220-013-1784-0 ER - TY - JOUR T1 - Interpolatability distinguishes LOCC from separable von Neumann measurements JF - Journal of Mathematical Physics Y1 - 2013 A1 - Andrew M. Childs A1 - Debbie Leung A1 - Laura Mancinska A1 - Maris Ozols AB - Local operations with classical communication (LOCC) and separable operations are two classes of quantum operations that play key roles in the study of quantum entanglement. Separable operations are strictly more powerful than LOCC, but no simple explanation of this phenomenon is known. We show that, in the case of von Neumann measurements, the ability to interpolate measurements is an operational principle that sets apart LOCC and separable operations. VL - 54 U4 - 112204 UR - http://arxiv.org/abs/1306.5992v1 CP - 11 J1 - J. Math. Phys. U5 - 10.1063/1.4830335 ER - TY - JOUR T1 - Product Formulas for Exponentials of Commutators JF - Journal of Mathematical Physics Y1 - 2013 A1 - Andrew M. Childs A1 - Nathan Wiebe AB - We provide a recursive method for constructing product formula approximations to exponentials of commutators, giving the first approximations that are accurate to arbitrarily high order. Using these formulas, we show how to approximate unitary exponentials of (possibly nested) commutators using exponentials of the elementary operators, and we upper bound the number of elementary exponentials needed to implement the desired operation within a given error tolerance. By presenting an algorithm for quantum search using evolution according to a commutator, we show that the scaling of the number of exponentials in our product formulas with the evolution time is nearly optimal. Finally, we discuss applications of our product formulas to quantum control and to implementing anticommutators, providing new methods for simulating many-body interaction Hamiltonians. VL - 54 U4 - 062202 UR - http://arxiv.org/abs/1211.4945v2 CP - 6 J1 - J. Math. Phys. U5 - 10.1063/1.4811386 ER - TY - JOUR T1 - A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates Y1 - 2013 A1 - Andrew M. Childs A1 - Stacey Jeffery A1 - Robin Kothari A1 - Frederic Magniez AB - We present an extension to the quantum walk search framework that facilitates quantum walks with nested updates. We apply it to give a quantum walk algorithm for 3-Distinctness with query complexity ~O(n^{5/7}), matching the best known upper bound (obtained via learning graphs) up to log factors. Furthermore, our algorithm has time complexity ~O(n^{5/7}), improving the previous ~O(n^{3/4}). UR - http://arxiv.org/abs/1302.7316v1 ER - TY - JOUR T1 - Universal computation by multi-particle quantum walk JF - Science Y1 - 2013 A1 - Andrew M. Childs A1 - David Gosset A1 - Zak Webb AB - A quantum walk is a time-homogeneous quantum-mechanical process on a graph defined by analogy to classical random walk. The quantum walker is a particle that moves from a given vertex to adjacent vertices in quantum superposition. Here we consider a generalization of quantum walk to systems with more than one walker. A continuous-time multi-particle quantum walk is generated by a time-independent Hamiltonian with a term corresponding to a single-particle quantum walk for each particle, along with an interaction term. Multi-particle quantum walk includes a broad class of interacting many-body systems such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions. We show that multi-particle quantum walk is capable of universal quantum computation. Since it is also possible to efficiently simulate a multi-particle quantum walk of the type we consider using a universal quantum computer, this model exactly captures the power of quantum computation. In principle our construction could be used as an architecture for building a scalable quantum computer with no need for time-dependent control. VL - 339 U4 - 791 - 794 UR - http://arxiv.org/abs/1205.3782v2 CP - 6121 J1 - Science U5 - 10.1126/science.1229957 ER - TY - JOUR T1 - Hamiltonian Simulation Using Linear Combinations of Unitary Operations JF - Quantum Information and Computation Y1 - 2012 A1 - Andrew M. Childs A1 - Nathan Wiebe AB - We present a new approach to simulating Hamiltonian dynamics based on implementing linear combinations of unitary operations rather than products of unitary operations. The resulting algorithm has superior performance to existing simulation algorithms based on product formulas and, most notably, scales better with the simulation error than any known Hamiltonian simulation technique. Our main tool is a general method to nearly deterministically implement linear combinations of nearby unitary operations, which we show is optimal among a large class of methods. VL - 12 U4 - 901-924 UR - http://arxiv.org/abs/1202.5822v1 CP - 11-12 J1 - Quantum Information and Computation 12 ER - TY - JOUR T1 - Levinson's theorem for graphs II JF - Journal of Mathematical Physics Y1 - 2012 A1 - Andrew M. Childs A1 - David Gosset AB - We prove Levinson's theorem for scattering on an (m+n)-vertex graph with n semi-infinite paths each attached to a different vertex, generalizing a previous result for the case n=1. This theorem counts the number of bound states in terms of the winding of the determinant of the S-matrix. We also provide a proof that the bound states and incoming scattering states of the Hamiltonian together form a complete basis for the Hilbert space, generalizing another result for the case n=1. VL - 53 U4 - 102207 UR - http://arxiv.org/abs/1203.6557v2 CP - 10 J1 - J. Math. Phys. U5 - 10.1063/1.4757665 ER - TY - JOUR T1 - The quantum query complexity of read-many formulas JF - Lecture Notes in Computer Science Y1 - 2012 A1 - Andrew M. Childs A1 - Shelby Kimmel A1 - Robin Kothari AB - The quantum query complexity of evaluating any read-once formula with n black-box input bits is Theta(sqrt(n)). However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with n inputs, size S, and G gates using O(min{n, sqrt{S}, n^{1/2} G^{1/4}}) quantum queries. Furthermore, we show that this algorithm is optimal, since for any n,S,G there exists a formula with n inputs, size at most S, and at most G gates that requires Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}}) queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth k >= 3, and we give a linear-size circuit of depth 2 that requires Omega (n^{5/9}) queries. Applications of these results include a Omega (n^{19/18}) lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including PARITY, and a construction of an AC^0 circuit of linear size that can only be evaluated by a formula with Omega(n^{2-epsilon}) gates. VL - 7501 U4 - 337-348 UR - http://arxiv.org/abs/1112.0548v1 J1 - Lecture Notes in Computer Science 7501 U5 - 10.1007/978-3-642-33090-2_30 ER - TY - JOUR T1 - Levinson's theorem for graphs JF - Journal of Mathematical Physics Y1 - 2011 A1 - Andrew M. Childs A1 - DJ Strouse AB - We prove an analog of Levinson's theorem for scattering on a weighted (m+1)-vertex graph with a semi-infinite path attached to one of its vertices. In particular, we show that the number of bound states in such a scattering problem is equal to m minus half the winding number of the phase of the reflection coefficient (where each so-called half-bound state is counted as half a bound state). VL - 52 U4 - 082102 UR - http://arxiv.org/abs/1103.5077v2 CP - 8 J1 - J. Math. Phys. U5 - 10.1063/1.3622608 ER - TY - JOUR T1 - Quantum query complexity of minor-closed graph properties JF - Proc. 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics Y1 - 2011 A1 - Andrew M. Childs A1 - Robin Kothari AB - We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether an $n$-vertex graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity \Theta(n^{3/2}). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n^{3/2}) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems. VL - 9 U4 - 661-672 UR - http://arxiv.org/abs/1011.1443v2 J1 - Proc. 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011) U5 - 10.4230/LIPIcs.STACS.2011.661 ER - TY - JOUR T1 - Characterization of universal two-qubit Hamiltonians Y1 - 2010 A1 - Andrew M. Childs A1 - Debbie Leung A1 - Laura Mancinska A1 - Maris Ozols AB - Suppose we can apply a given 2-qubit Hamiltonian H to any (ordered) pair of qubits. We say H is n-universal if it can be used to approximate any unitary operation on n qubits. While it is well known that almost any 2-qubit Hamiltonian is 2-universal (Deutsch, Barenco, Ekert 1995; Lloyd 1995), an explicit characterization of the set of non-universal 2-qubit Hamiltonians has been elusive. Our main result is a complete characterization of 2-non-universal 2-qubit Hamiltonians. In particular, there are three ways that a 2-qubit Hamiltonian H can fail to be universal: (1) H shares an eigenvector with the gate that swaps two qubits, (2) H acts on the two qubits independently (in any of a certain family of bases), or (3) H has zero trace. A 2-non-universal 2-qubit Hamiltonian can still be n-universal for some n >= 3. We give some partial results on 3-universality. Finally, we also show how our characterization of 2-universal Hamiltonians implies the well-known result that almost any 2-qubit unitary is universal. UR - http://arxiv.org/abs/1004.1645v2 J1 - Quantum Information and Computation 11 ER - TY - JOUR T1 - Quantum algorithms for algebraic problems JF - Reviews of Modern Physics Y1 - 2010 A1 - Andrew M. Childs A1 - Wim van Dam AB - Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation, and in particular, on problems with an algebraic flavor. VL - 82 U4 - 1 - 52 UR - http://arxiv.org/abs/0812.0380v1 CP - 1 J1 - Rev. Mod. Phys. U5 - 10.1103/RevModPhys.82.1 ER - TY - JOUR T1 - Quantum property testing for bounded-degree graphs JF - Proc. RANDOM Y1 - 2010 A1 - Andris Ambainis A1 - Andrew M. Childs A1 - Yi-Kai Liu AB - We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure. U4 - 365-376 UR - http://arxiv.org/abs/1012.3174v3 J1 - Proceedings of RANDOM 2011 U5 - 10.1007/978-3-642-22935-0_31 ER - TY - JOUR T1 - On the relationship between continuous- and discrete-time quantum walk JF - Communications in Mathematical Physics Y1 - 2010 A1 - Andrew M. Childs AB - Quantum walk is one of the main tools for quantum algorithms. Defined by analogy to classical random walk, a quantum walk is a time-homogeneous quantum process on a graph. Both random and quantum walks can be defined either in continuous or discrete time. But whereas a continuous-time random walk can be obtained as the limit of a sequence of discrete-time random walks, the two types of quantum walk appear fundamentally different, owing to the need for extra degrees of freedom in the discrete-time case. In this article, I describe a precise correspondence between continuous- and discrete-time quantum walks on arbitrary graphs. Using this correspondence, I show that continuous-time quantum walk can be obtained as an appropriate limit of discrete-time quantum walks. The correspondence also leads to a new technique for simulating Hamiltonian dynamics, giving efficient simulations even in cases where the Hamiltonian is not sparse. The complexity of the simulation is linear in the total evolution time, an improvement over simulations based on high-order approximations of the Lie product formula. As applications, I describe a continuous-time quantum walk algorithm for element distinctness and show how to optimally simulate continuous-time query algorithms of a certain form in the conventional quantum query model. Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations. VL - 294 U4 - 581 - 603 UR - http://arxiv.org/abs/0810.0312v3 CP - 2 J1 - Commun. Math. Phys. U5 - 10.1007/s00220-009-0930-1 ER - TY - JOUR T1 - Simulating sparse Hamiltonians with star decompositions Y1 - 2010 A1 - Andrew M. Childs A1 - Robin Kothari AB - We present an efficient algorithm for simulating the time evolution due to a sparse Hamiltonian. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian H acts for time t, this algorithm uses (d^2(d+log* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log* N)||Ht||)^{1+o(1)}. To achieve this, we decompose a general sparse Hamiltonian into a small sum of Hamiltonians whose graphs of non-zero entries have the property that every connected component is a star, and efficiently simulate each of these pieces. UR - http://arxiv.org/abs/1003.3683v2 J1 - Theory of Quantum Computation U5 - 10.1007/978-3-642-18073-6_8 ER - TY - JOUR T1 - Black-box Hamiltonian simulation and unitary implementation Y1 - 2009 A1 - Dominic W. Berry A1 - Andrew M. Childs AB - We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D^4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N x N unitary operation use O(N^2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(sqrt{N}) queries, which is optimal. UR - http://arxiv.org/abs/0910.4157v4 J1 - Quantum Information and Computation 12 ER - TY - JOUR T1 - Discrete-query quantum algorithm for NAND trees JF - Theory of Computing Y1 - 2009 A1 - Andrew M. Childs A1 - Richard Cleve A1 - Stephen P. Jordan A1 - David Yeung AB - Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0. VL - 5 U4 - 119 - 123 UR - http://arxiv.org/abs/quant-ph/0702160v1 CP - 1 J1 - Theory of Comput. U5 - 10.4086/toc.2009.v005a005 ER - TY - JOUR T1 - Limitations on the simulation of non-sparse Hamiltonians Y1 - 2009 A1 - Andrew M. Childs A1 - Robin Kothari AB - The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N x N Hamiltonian H for time t can be simulated using O(||Ht||poly(log N)) operations, which is essentially optimal due to a no--fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian $H$. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity. UR - http://arxiv.org/abs/0908.4398v2 J1 - Quantum Information and Computation 10 ER - TY - JOUR T1 - The quantum query complexity of certification Y1 - 2009 A1 - Andris Ambainis A1 - Andrew M. Childs A1 - François Le Gall A1 - Seiichiro Tani AB - We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem. UR - http://arxiv.org/abs/0903.1291v2 J1 - Quantum Information and Computation 10 ER - TY - JOUR T1 - Universal computation by quantum walk JF - Physical Review Letters Y1 - 2009 A1 - Andrew M. Childs AB - In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes. VL - 102 UR - http://arxiv.org/abs/0806.1972v1 CP - 18 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.102.180501 ER - TY - JOUR T1 - Every NAND formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer Y1 - 2007 A1 - Andrew M. Childs A1 - Ben W. Reichardt A1 - Robert Spalek A1 - Shengyu Zhang AB - For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time quantum algorithm, based on a coined quantum walk, that evaluates this formula on a black-box input. Balanced, or ``approximately balanced,'' NAND formulas can be evaluated in O(sqrt{N}) queries, which is optimal. It follows that the (2-o(1))-th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy. UR - http://arxiv.org/abs/quant-ph/0703015v3 ER - TY - JOUR T1 - Improved quantum algorithms for the ordered search problem via semidefinite programming JF - Physical Review A Y1 - 2007 A1 - Andrew M. Childs A1 - Andrew J. Landahl A1 - Pablo A. Parrilo AB - One of the most basic computational problems is the task of finding a desired item in an ordered list of N items. While the best classical algorithm for this problem uses log_2 N queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for ordered search in terms of a semidefinite program, we find new quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using 4 log_{605} N \approx 0.433 log_2 N queries, which improves upon the previously best known exact algorithm. VL - 75 UR - http://arxiv.org/abs/quant-ph/0608161v1 CP - 3 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.75.032335 ER - TY - JOUR T1 - The limitations of nice mutually unbiased bases JF - Journal of Algebraic Combinatorics Y1 - 2007 A1 - Michael Aschbacher A1 - Andrew M. Childs A1 - Pawel Wocjan AB - Mutually unbiased bases of a Hilbert space can be constructed by partitioning a unitary error basis. We consider this construction when the unitary error basis is a nice error basis. We show that the number of resulting mutually unbiased bases can be at most one plus the smallest prime power contained in the dimension, and therefore that this construction cannot improve upon previous approaches. We prove this by establishing a correspondence between nice mutually unbiased bases and abelian subgroups of the index group of a nice error basis and then bounding the number of such subgroups. This bound also has implications for the construction of certain combinatorial objects called nets. VL - 25 U4 - 111 - 123 UR - http://arxiv.org/abs/quant-ph/0412066v1 CP - 2 J1 - J Algebr Comb U5 - 10.1007/s10801-006-0002-y ER - TY - JOUR T1 - Optimal quantum adversary lower bounds for ordered search Y1 - 2007 A1 - Andrew M. Childs A1 - Troy Lee AB - The goal of the ordered search problem is to find a particular item in an ordered list of n items. Using the adversary method, Hoyer, Neerbek, and Shi proved a quantum lower bound for this problem of (1/pi) ln n + Theta(1). Here, we find the exact value of the best possible quantum adversary lower bound for a symmetrized version of ordered search (whose query complexity differs from that of the original problem by at most 1). Thus we show that the best lower bound for ordered search that can be proved by the adversary method is (1/pi) ln n + O(1). Furthermore, we show that this remains true for the generalized adversary method allowing negative weights. UR - http://arxiv.org/abs/0708.3396v1 J1 - Proc. 35th International Colloquium on Automata U5 - 10.1007/978-3-540-70575-8_71 ER - TY - JOUR T1 - Quantum algorithms for hidden nonlinear structures Y1 - 2007 A1 - Andrew M. Childs A1 - Leonard J. Schulman A1 - Umesh V. Vazirani AB - Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonabelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures. UR - http://arxiv.org/abs/0705.2784v1 J1 - Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS 2007) U5 - 10.1109/FOCS.2007.18 ER - TY - JOUR T1 - Two-way quantum communication channels JF - International Journal of Quantum Information Y1 - 2006 A1 - Andrew M. Childs A1 - Debbie W. Leung A1 - Hoi-Kwong Lo AB - We consider communication between two parties using a bipartite quantum operation, which constitutes the most general quantum mechanical model of two-party communication. We primarily focus on the simultaneous forward and backward communication of classical messages. For the case in which the two parties share unlimited prior entanglement, we give inner and outer bounds on the achievable rate region that generalize classical results due to Shannon. In particular, using a protocol of Bennett, Harrow, Leung, and Smolin, we give a one-shot expression in terms of the Holevo information for the entanglement-assisted one-way capacity of a two-way quantum channel. As applications, we rederive two known additivity results for one-way channel capacities: the entanglement-assisted capacity of a general one-way channel, and the unassisted capacity of an entanglement-breaking one-way channel. VL - 04 U4 - 63 - 83 UR - http://arxiv.org/abs/quant-ph/0506039v1 CP - 01 J1 - Int. J. Quanum Inform. U5 - 10.1142/S0219749906001621 ER - TY - JOUR T1 - Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem Y1 - 2006 A1 - Andrew M. Childs A1 - Aram W. Harrow A1 - Pawel Wocjan AB - Schur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur duality to the problem of distinguishing coset states in the standard approach to the hidden subgroup problem. We observe that simply measuring the partition (a procedure we call weak Schur sampling) provides very little information about the hidden subgroup. Furthermore, we show that under quite general assumptions, even a combination of weak Fourier sampling and weak Schur sampling fails to identify the hidden subgroup. We also prove tight bounds on how many coset states are required to solve the hidden subgroup problem by weak Schur sampling, and we relate this question to a quantum version of the collision problem. UR - http://arxiv.org/abs/quant-ph/0609110v1 J1 - Proc. 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007) U5 - 10.1007/978-3-540-70918-3_51 ER - TY - JOUR T1 - From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups Y1 - 2005 A1 - Dave Bacon A1 - Andrew M. Childs A1 - Wim van Dam AB - We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including the Heisenberg group, r=2). In particular, our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP. UR - http://arxiv.org/abs/quant-ph/0504083v2 J1 - Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005) U5 - 10.1109/SFCS.2005.38 ER - TY - JOUR T1 - Optimal measurements for the dihedral hidden subgroup problem Y1 - 2005 A1 - Dave Bacon A1 - Andrew M. Childs A1 - Wim van Dam AB - We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement. UR - http://arxiv.org/abs/quant-ph/0501044v2 J1 - Chicago Journal of Theoretical Computer Science (2006) ER - TY - JOUR T1 - Quantum algorithm for a generalized hidden shift problem Y1 - 2005 A1 - Andrew M. Childs A1 - Wim van Dam AB - Consider the following generalized hidden shift problem: given a function f on {0,...,M-1} x Z_N satisfying f(b,x)=f(b+1,x+s) for b=0,1,...,M-2, find the unknown shift s in Z_N. For M=N, this problem is an instance of the abelian hidden subgroup problem, which can be solved efficiently on a quantum computer, whereas for M=2, it is equivalent to the dihedral hidden subgroup problem, for which no efficient algorithm is known. For any fixed positive epsilon, we give an efficient (i.e., poly(log N)) quantum algorithm for this problem provided M > N^epsilon. The algorithm is based on the "pretty good measurement" and uses H. Lenstra's (classical) algorithm for integer programming as a subroutine. UR - http://arxiv.org/abs/quant-ph/0507190v1 J1 - Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007) ER - TY - JOUR T1 - On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems Y1 - 2005 A1 - Andrew M. Childs A1 - Pawel Wocjan AB - We consider an approach to deciding isomorphism of rigid n-vertex graphs (and related isomorphism problems) by solving a nonabelian hidden shift problem on a quantum computer using the standard method. Such an approach is arguably more natural than viewing the problem as a hidden subgroup problem. We prove that the hidden shift approach to rigid graph isomorphism is hard in two senses. First, we prove that Omega(n) copies of the hidden shift states are necessary to solve the problem (whereas O(n log n) copies are sufficient). Second, we prove that if one is restricted to single-register measurements, an exponential number of hidden shift states are required. UR - http://arxiv.org/abs/quant-ph/0510185v1 J1 - Quantum Information and Computation ER - TY - JOUR T1 - Unified derivations of measurement-based schemes for quantum computation JF - Physical Review A Y1 - 2005 A1 - Andrew M. Childs A1 - Debbie W. Leung A1 - Michael A. Nielsen AB - We present unified, systematic derivations of schemes in the two known measurement-based models of quantum computation. The first model (introduced by Raussendorf and Briegel [Phys. Rev. Lett., 86, 5188 (2001)]) uses a fixed entangled state, adaptive measurements on single qubits, and feedforward of the measurement results. The second model (proposed by Nielsen [Phys. Lett. A, 308, 96 (2003)] and further simplified by Leung [Int. J. Quant. Inf., 2, 33 (2004)]) uses adaptive two-qubit measurements that can be applied to arbitrary pairs of qubits, and feedforward of the measurement results. The underlying principle of our derivations is a variant of teleportation introduced by Zhou, Leung, and Chuang [Phys. Rev. A, 62, 052316 (2000)]. Our derivations unify these two measurement-based models of quantum computation and provide significantly simpler schemes. VL - 71 UR - http://arxiv.org/abs/quant-ph/0404132v2 CP - 3 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.71.032318 ER - TY - JOUR T1 - Reversible simulation of bipartite product Hamiltonians JF - IEEE Transactions on Information Theory Y1 - 2004 A1 - Andrew M. Childs A1 - Debbie W. Leung A1 - Guifre Vidal AB - Consider two quantum systems A and B interacting according to a product Hamiltonian H = H_A x H_B. We show that any two such Hamiltonians can be used to simulate each other reversibly (i.e., without efficiency losses) with the help of local unitary operations and local ancillas. Accordingly, all non-local features of a product Hamiltonian -- including the rate at which it can be used to produce entanglement, transmit classical or quantum information, or simulate other Hamiltonians -- depend only upon a single parameter. We identify this parameter and use it to obtain an explicit expression for the entanglement capacity of all product Hamiltonians. Finally, we show how the notion of simulation leads to a natural formulation of measures of the strength of a nonlocal Hamiltonian. VL - 50 U4 - 1189 - 1197 UR - http://arxiv.org/abs/quant-ph/0303097v1 CP - 6 J1 - IEEE Trans. Inform. Theory U5 - 10.1109/TIT.2004.828069 ER - TY - JOUR T1 - Spatial search and the Dirac equation JF - Physical Review A Y1 - 2004 A1 - Andrew M. Childs A1 - Jeffrey Goldstone AB - We consider the problem of searching a d-dimensional lattice of N sites for a single marked location. We present a Hamiltonian that solves this problem in time of order sqrt(N) for d>2 and of order sqrt(N) log(N) in the critical dimension d=2. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of d=4), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom. VL - 70 UR - http://arxiv.org/abs/quant-ph/0405120v1 CP - 4 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.70.042312 ER - TY - JOUR T1 - Spatial search by quantum walk JF - Physical Review A Y1 - 2004 A1 - Andrew M. Childs A1 - Jeffrey Goldstone AB - Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of N items laid out in d spatial dimensions can be searched in time of order sqrt(N) for d>2, and in time of order sqrt(N) poly(log N) for d=2. We consider an alternative search algorithm based on a continuous time quantum walk on a graph. The case of the complete graph gives the continuous time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that sqrt(N) speedup can also be achieved on the hypercube. We show that full sqrt(N) speedup can be achieved on a d-dimensional periodic lattice for d>4. In d=4, the quantum walk search algorithm takes time of order sqrt(N) poly(log N), and in d<4, the algorithm does not provide substantial speedup. VL - 70 UR - http://arxiv.org/abs/quant-ph/0306054v2 CP - 2 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.70.022314 ER - TY - JOUR T1 - Lower bounds on the complexity of simulating quantum gates JF - Physical Review A Y1 - 2003 A1 - Andrew M. Childs A1 - Henry L. Haselgrove A1 - Michael A. Nielsen AB - We give a simple proof of a formula for the minimal time required to simulate a two-qubit unitary operation using a fixed two-qubit Hamiltonian together with fast local unitaries. We also note that a related lower bound holds for arbitrary n-qubit gates. VL - 68 UR - http://arxiv.org/abs/quant-ph/0307190v1 CP - 5 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.68.052311 ER - TY - JOUR T1 - Quantum algorithms for subset finding Y1 - 2003 A1 - Andrew M. Childs A1 - Jason M. Eisenberg AB - Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds. UR - http://arxiv.org/abs/quant-ph/0311038v2 J1 - Quantum Information and Computation 5 ER - TY - JOUR T1 - Asymptotic entanglement capacity of the Ising and anisotropic Heisenberg interactions Y1 - 2002 A1 - A. M. Childs A1 - D. W. Leung A1 - F. Verstraete A1 - G. Vidal AB - We compute the asymptotic entanglement capacity of the Ising interaction ZZ, the anisotropic Heisenberg interaction XX + YY, and more generally, any two-qubit Hamiltonian with canonical form K = a XX + b YY. We also describe an entanglement assisted classical communication protocol using the Hamiltonian K with rate equal to the asymptotic entanglement capacity. UR - http://arxiv.org/abs/quant-ph/0207052v2 J1 - Quantum Information and Computation 3 ER - TY - JOUR T1 - Exponential algorithmic speedup by quantum walk Y1 - 2002 A1 - Andrew M. Childs A1 - Richard Cleve A1 - Enrico Deotto A1 - Edward Farhi A1 - Sam Gutmann A1 - Daniel A. Spielman AB - We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve this problem with high probability in subexponential time. UR - http://arxiv.org/abs/quant-ph/0209131v2 J1 - Proc. 35th ACM Symposium on Theory of Computing (STOC 2003) U5 - 10.1145/780542.780552 ER - TY - JOUR T1 - Quantum search by measurement JF - Physical Review A Y1 - 2002 A1 - Andrew M. Childs A1 - Enrico Deotto A1 - Edward Farhi A1 - Jeffrey Goldstone A1 - Sam Gutmann A1 - Andrew J. Landahl AB - We propose a quantum algorithm for solving combinatorial search problems that uses only a sequence of measurements. The algorithm is similar in spirit to quantum computation by adiabatic evolution, in that the goal is to remain in the ground state of a time-varying Hamiltonian. Indeed, we show that the running times of the two algorithms are closely related. We also show how to achieve the quadratic speedup for Grover's unstructured search problem with only two measurements. Finally, we discuss some similarities and differences between the adiabatic and measurement algorithms. VL - 66 UR - http://arxiv.org/abs/quant-ph/0204013v1 CP - 3 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.66.032314 ER - TY - JOUR T1 - Universal simulation of Hamiltonian dynamics for qudits JF - Physical Review A Y1 - 2002 A1 - Michael A. Nielsen A1 - Michael J. Bremner A1 - Jennifer L. Dodd A1 - Andrew M. Childs A1 - Christopher M. Dawson AB - What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? Dodd et al. (quant-ph/0106064) provided a partial solution to this problem in the form of an efficient algorithm to simulate any desired two-body Hamiltonian evolution using any fixed two-body entangling N-qubit Hamiltonian, and local unitaries. We extend this result to the case where the component systems have D dimensions. As a consequence we explain how universal quantum computation can be performed with any fixed two-body entangling N-qudit Hamiltonian, and local unitaries. VL - 66 UR - http://arxiv.org/abs/quant-ph/0109064v2 CP - 2 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.66.022317 ER - TY - JOUR T1 - Exact sampling from non-attractive distributions using summary states JF - Physical Review E Y1 - 2001 A1 - Andrew M. Childs A1 - Ryan B. Patterson A1 - David J. C. MacKay AB - Propp and Wilson's method of coupling from the past allows one to efficiently generate exact samples from attractive statistical distributions (e.g., the ferromagnetic Ising model). This method may be generalized to non-attractive distributions by the use of summary states, as first described by Huber. Using this method, we present exact samples from a frustrated antiferromagnetic triangular Ising model and the antiferromagnetic q=3 Potts model. We discuss the advantages and limitations of the method of summary states for practical sampling, paying particular attention to the slowing down of the algorithm at low temperature. In particular, we show that such a slowing down can occur in the absence of a physical phase transition. VL - 63 UR - http://arxiv.org/abs/cond-mat/0005132v1 CP - 3 J1 - Phys. Rev. E U5 - 10.1103/PhysRevE.63.036113 ER - TY - JOUR T1 - An example of the difference between quantum and classical random walks JF - Quantum Information Processing Y1 - 2001 A1 - Andrew M. Childs A1 - Edward Farhi A1 - Sam Gutmann AB - In this note, we discuss a general definition of quantum random walks on graphs and illustrate with a simple graph the possibility of very different behavior between a classical random walk and its quantum analogue. In this graph, propagation between a particular pair of nodes is exponentially faster in the quantum case. VL - 1 U4 - 35 - 43 UR - http://arxiv.org/abs/quant-ph/0103020v1 CP - 1/2 J1 - Quantum Information Processing 1 U5 - 10.1023/A:1019609420309 ER - TY - JOUR T1 - Realization of quantum process tomography in NMR JF - Physical Review A Y1 - 2001 A1 - Andrew M. Childs A1 - Isaac L. Chuang A1 - Debbie W. Leung AB - Quantum process tomography is a procedure by which the unknown dynamical evolution of an open quantum system can be fully experimentally characterized. We demonstrate explicitly how this procedure can be implemented with a nuclear magnetic resonance quantum computer. This allows us to measure the fidelity of a controlled-not logic gate and to experimentally investigate the error model for our computer. Based on the latter analysis, we test an important assumption underlying nearly all models of quantum error correction, the independence of errors on different qubits. VL - 64 UR - http://arxiv.org/abs/quant-ph/0012032v1 CP - 1 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.64.012314 ER - TY - JOUR T1 - Robustness of adiabatic quantum computation JF - Physical Review A Y1 - 2001 A1 - Andrew M. Childs A1 - Edward Farhi A1 - John Preskill AB - We study the fault tolerance of quantum computation by adiabatic evolution, a quantum algorithm for solving various combinatorial search problems. We describe an inherent robustness of adiabatic computation against two kinds of errors, unitary control errors and decoherence, and we study this robustness using numerical simulations of the algorithm. VL - 65 UR - http://arxiv.org/abs/quant-ph/0108048v1 CP - 1 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.65.012322 ER - TY - JOUR T1 - Secure assisted quantum computation Y1 - 2001 A1 - Andrew M. Childs AB - Suppose Alice wants to perform some computation that could be done quickly on a quantum computer, but she cannot do universal quantum computation. Bob can do universal quantum computation and claims he is willing to help, but Alice wants to be sure that Bob cannot learn her input, the result of her calculation, or perhaps even the function she is trying to compute. We describe a simple, efficient protocol by which Bob can help Alice perform the computation, but there is no way for him to learn anything about it. We also discuss techniques for Alice to detect whether Bob is honestly helping her or if he is introducing errors. UR - http://arxiv.org/abs/quant-ph/0111046v2 J1 - Quantum Information and Computation 5 ER - TY - JOUR T1 - Universal simulation of Markovian quantum dynamics JF - Physical Review A Y1 - 2001 A1 - Dave Bacon A1 - Andrew M. Childs A1 - Isaac L. Chuang A1 - Julia Kempe A1 - Debbie W. Leung A1 - Xinlan Zhou AB - Although the conditions for performing arbitrary unitary operations to simulate the dynamics of a closed quantum system are well understood, the same is not true of the more general class of quantum operations (also known as superoperators) corresponding to the dynamics of open quantum systems. We propose a framework for the generation of Markovian quantum dynamics and study the resources needed for universality. For the case of a single qubit, we show that a single nonunitary process is necessary and sufficient to generate all unital Markovian quantum dynamics, whereas a set of processes parametrized by one continuous parameter is needed in general. We also obtain preliminary results for the unital case in higher dimensions. VL - 64 UR - http://arxiv.org/abs/quant-ph/0008070v2 CP - 6 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.64.062302 ER - TY - JOUR T1 - Finding cliques by quantum adiabatic evolution Y1 - 2000 A1 - Andrew M. Childs A1 - Edward Farhi A1 - Jeffrey Goldstone A1 - Sam Gutmann AB - Quantum adiabatic evolution provides a general technique for the solution of combinatorial search problems on quantum computers. We present the results of a numerical study of a particular application of quantum adiabatic evolution, the problem of finding the largest clique in a random graph. An n-vertex random graph has each edge included with probability 1/2, and a clique is a completely connected subgraph. There is no known classical algorithm that finds the largest clique in a random graph with high probability and runs in a time polynomial in n. For the small graphs we are able to investigate (n <= 18), the quantum algorithm appears to require only a quadratic run time. UR - http://arxiv.org/abs/quant-ph/0012104v1 J1 - Quantum Information and Computation 2 ER - TY - JOUR T1 - Quantum information and precision measurement JF - Journal of Modern Optics Y1 - 2000 A1 - Andrew M. Childs A1 - John Preskill A1 - Joseph Renes AB - We describe some applications of quantum information theory to the analysis of quantum limits on measurement sensitivity. A measurement of a weak force acting on a quantum system is a determination of a classical parameter appearing in the master equation that governs the evolution of the system; limitations on measurement accuracy arise because it is not possible to distinguish perfectly among the different possible values of this parameter. Tools developed in the study of quantum information and computation can be exploited to improve the precision of physics experiments; examples include superdense coding, fast database search, and the quantum Fourier transform. VL - 47 U4 - 155 - 176 UR - http://arxiv.org/abs/quant-ph/9904021v2 CP - 2-3 J1 - Journal of Modern Optics U5 - 10.1080/09500340008244034 ER - TY - JOUR T1 - Universal quantum computation with two-level trapped ions JF - Physical Review A Y1 - 2000 A1 - Andrew M. Childs A1 - Isaac L. Chuang AB - Although the initial proposal for ion trap quantum computation made use of an auxiliary internal level to perform logic between ions, this resource is not necessary in principle. Instead, one may perform such operations directly using sideband laser pulses, operating with an arbitrary (sufficiently small) Lamb-Dicke parameter. We explore the potential of this technique, showing how to perform logical operations between the internal state of an ion and the collective motional state and giving explicit constructions for a controlled-not gate between ions. VL - 63 UR - http://arxiv.org/abs/quant-ph/0008065v1 CP - 1 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.63.012306 ER -