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.

}, doi = {https://doi.org/10.4230/LIPIcs.TQC.2019.3}, url = {https://arxiv.org/abs/1902.09102}, author = {Andrew M. Childs and Eddie Schoute and Cem M. Unsal} } @article {2195, title = {Locality and digital quantum simulation of power-law interactions}, journal = {Phys. Rev. X 9, 031006}, volume = {9}, year = {2019}, month = {07/10/2019}, abstract = {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).

}, doi = {https://doi.org/10.1103/PhysRevX.9.031006}, url = {https://arxiv.org/abs/1808.05225}, author = {Minh Cong Tran and Andrew Y. Guo and Yuan Su and James R. Garrison and Zachary Eldredge and Michael Foss-Feig and Andrew M. Childs and Alexey V. Gorshkov} } @article {2332, title = {Nearly optimal lattice simulation by product formulas}, journal = {Physical Review Letters}, year = {2019}, abstract = {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.

}, url = {https://arxiv.org/abs/1901.00564}, author = {Andrew M. Childs and Yuan Su} } @article {2333, title = {Quantum spectral methods for differential equations}, year = {2019}, abstract = {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/ε)).

}, url = {https://arxiv.org/abs/1901.00961}, author = {Andrew M. Childs and Jin-Peng Liu} } @article {2403, title = {Signaling and Scrambling with Strongly Long-Range Interactions}, year = {2019}, month = {06/06/2019}, abstract = {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.\

}, url = {https://arxiv.org/abs/1906.02662}, author = {Andrew Y. Guo and Minh C. Tran and Andrew M. Childs and Alexey V. Gorshkov and Zhe-Xuan Gong} } @article {2402, title = {Time-dependent Hamiltonian simulation with L1-norm scaling}, year = {2019}, month = {06/17/2019}, abstract = {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{\"o}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.

}, url = {https://arxiv.org/abs/1906.07115}, author = {Dominic W. Berry and Andrew M. Childs and Yuan Su and Xin Wang and Nathan Wiebe} } @article {2067, title = {Automated optimization of large quantum circuits with continuous parameters}, journal = {npj:Quantum Information}, volume = {4}, year = {2018}, month = {2017/10/19}, abstract = {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.\

}, doi = {https://doi.org/10.1038/s41534-018-0072-4}, url = {https://arxiv.org/abs/1710.07345}, author = {Yunseong Nam and Neil J. Ross and Yuan Su and Andrew M. Childs and Dmitri Maslov} } @article {2174, title = {Faster quantum simulation by randomization}, year = {2018}, month = {2018/05/22}, abstract = {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.

}, url = {https://arxiv.org/abs/1805.08385}, author = {Andrew M. Childs and Aaron Ostrander and Yuan Su} } @article {1922, title = {Quantum algorithm for multivariate polynomial interpolation}, journal = {Proceedings of The Royal Society A}, volume = {474}, year = {2018}, month = {2018/01/17}, abstract = {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.

}, doi = {10.1098/rspa.2017.0480}, url = {http://rspa.royalsocietypublishing.org/content/474/2209/20170480}, author = {Jianxin Chen and Andrew M. Childs and Shih-Han Hung} } @article {2207, title = {Quantum algorithms and lower bounds for convex optimization}, year = {2018}, abstract = {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.

}, url = {https://arxiv.org/abs/1809.01731}, author = {Shouvanik Chakrabarti and Andrew M. Childs and Tongyang Li and Xiaodi Wu} } @article {2220, title = {Toward the first quantum simulation with quantum speedup}, journal = {Proceedings of the National Academy of Sciences}, volume = {115 }, year = {2018}, pages = {9456-9461}, abstract = {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.

}, doi = {https://doi.org/10.1073/pnas.1801723115}, url = {https://arxiv.org/abs/1711.10980}, author = {Andrew M. Childs and Dmitri Maslov and Yunseong Nam and Neil J. Ross and Yuan Su} } @article {1902, title = {Efficient simulation of sparse Markovian quantum dynamics}, journal = {Quantum Information and Computation}, volume = {17}, year = {2017}, month = {2017/09/01}, pages = {901-947}, abstract = {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.

}, doi = {10.26421/QIC17.11-12}, url = {https://arxiv.org/abs/1611.05543}, author = {Andrew M. Childs and Tongyang Li} } @article {1923, title = {Quantum algorithm for linear differential equations with exponentially improved dependence on precision}, journal = {Communications in Mathematical Physics}, volume = {356}, year = {2017}, month = {2017/12/01}, pages = {1057-1081}, abstract = {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.

}, url = {https://arxiv.org/abs/1701.03684}, author = {Dominic W. Berry and Andrew M. Childs and Aaron Ostrander and Guoming Wang} } @article {1605, title = {Quantum algorithm for systems of linear equations with exponentially improved dependence on precision}, journal = {SIAM Journal on Computing}, volume = {46}, year = {2017}, month = {2017/12/21}, pages = {1920-1950}, abstract = {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.

}, doi = {10.1137/16M1087072}, url = {http://epubs.siam.org/doi/10.1137/16M1087072}, author = {Andrew M. Childs and Robin Kothari and Rolando D. Somma} } @article {1234, title = {Complexity of the XY antiferromagnet at fixed magnetization}, journal = {Quantum Information and Computation}, volume = {16}, year = {2016}, month = {2016/01/01}, pages = {1-18}, abstract = { 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. }, url = {http://arxiv.org/abs/1503.07083v1}, author = {Andrew M. Childs and David Gosset and Zak Webb} } @article {1554, title = {Optimal quantum algorithm for polynomial interpolation}, journal = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, volume = {55}, year = {2016}, month = {2016/03/01}, pages = {16:1--16:13}, abstract = {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\&$\#$39;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.

}, isbn = {978-3-95977-013-2}, issn = {1868-8969}, doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.16}, url = {http://arxiv.org/abs/1509.09271}, author = {Andrew M. Childs and Wim van Dam and Shih-Han Hung and Igor E. Shparlinski} } @article {1235, title = {Optimal state discrimination and unstructured search in nonlinear quantum mechanics}, journal = {Physical Review A}, volume = {93}, year = {2016}, month = {2016/02/11}, pages = {022314}, abstract = { 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. }, doi = {10.1103/PhysRevA.93.022314}, url = {http://arxiv.org/abs/1507.06334}, author = {Andrew M. Childs and Joshua Young} } @article {1247, title = {Hamiltonian simulation with nearly optimal dependence on all parameters}, journal = {Proceedings of the 56th IEEE Symposium on Foundations of Computer Science}, year = {2015}, month = {2015/01/08}, pages = {792-809}, abstract = { 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$. }, doi = {10.1109/FOCS.2015.54}, url = {http://arxiv.org/abs/1501.01715}, author = {Dominic W. Berry and Andrew M. Childs and Robin Kothari} } @article {1259, title = {Momentum switches}, journal = {Quantum Information and Computation}, volume = {15}, year = {2015}, month = {2015/05/01}, pages = {601-621}, abstract = { 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. }, url = {http://arxiv.org/abs/1406.4510v1}, author = {Andrew M. Childs and David Gosset and Daniel Nagaj and Mouktik Raha and Zak Webb} } @article {1265, title = {Simulating Hamiltonian dynamics with a truncated Taylor series}, journal = {Physical Review Letters}, volume = {114}, year = {2015}, month = {2015/03/03}, pages = {090502}, abstract = { 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. }, doi = {10.1103/PhysRevLett.114.090502}, url = {http://arxiv.org/abs/1412.4687v1}, author = {Dominic W. Berry and Andrew M. Childs and Richard Cleve and Robin Kothari and Rolando D. Somma} } @article {1232, title = {The Bose-Hubbard model is QMA-complete}, journal = {Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014)}, volume = {8572}, year = {2014}, month = {2014/07/08}, pages = {308-319}, abstract = { 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. }, doi = {10.1007/978-3-662-43948-7_26}, url = {http://arxiv.org/abs/1311.3297v1}, author = {Andrew M. Childs and David Gosset and Zak Webb} } @article {1230, title = {The computational power of matchgates and the XY interaction on arbitrary graphs}, journal = {Quantum Information and Computation}, volume = {14}, year = {2014}, month = {2014/09/01}, pages = {901-916}, abstract = { 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. }, url = {http://arxiv.org/abs/1308.1463v1}, author = {Daniel J. Brod and Andrew M. Childs} } @article {1226, title = {Constructing elliptic curve isogenies in quantum subexponential time}, journal = {Journal of Mathematical Cryptology}, volume = {8}, year = {2014}, month = {2014/01/01}, pages = {1 - 29}, abstract = { 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{\textquoteright}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. }, doi = {10.1515/jmc-2012-0016}, url = {http://arxiv.org/abs/1012.4019v2}, author = {Andrew M. Childs and David Jao and Vladimir Soukharev} } @article {1264, title = {Exponential improvement in precision for simulating sparse Hamiltonians}, journal = {Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014)}, year = {2014}, month = {2014/05/31}, pages = {283-292}, abstract = { 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. }, isbn = {978-1-4503-2710-7}, doi = {10.1145/2591796.2591854}, url = {http://arxiv.org/abs/1312.1414v2}, author = {Dominic W. Berry and Andrew M. Childs and Richard Cleve and Robin Kothari and Rolando D. Somma} } @article {1231, title = {Quantum computation of discrete logarithms in semigroups}, journal = {Journal of Mathematical Cryptology}, volume = {8}, year = {2014}, month = {2014/01/1}, abstract = { We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor{\textquoteright}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. }, doi = {10.1515/jmc-2013-0038}, url = {http://arxiv.org/abs/1310.6238v2}, author = {Andrew M. Childs and G{\'a}bor Ivanyos} } @article {1233, title = {Spatial search by continuous-time quantum walks on crystal lattices}, journal = {Physical Review A}, volume = {89}, year = {2014}, month = {2014/5/30}, abstract = { 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. }, doi = {10.1103/PhysRevA.89.052337}, url = {http://arxiv.org/abs/1403.2676v2}, author = {Andrew M. Childs and Yimin Ge} } @article {1245, title = {Easy and hard functions for the Boolean hidden shift problem}, journal = {Proceedings of TQC 2013}, volume = {22}, year = {2013}, month = {2013/04/16}, pages = {50-79}, abstract = { 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. }, doi = {10.4230/LIPIcs.TQC.2013.50}, url = {http://arxiv.org/abs/1304.4642v1}, author = {Andrew M. Childs and Robin Kothari and Maris Ozols and Martin Roetteler} } @article {1244, title = {A framework for bounding nonlocality of state discrimination}, journal = {Communications in Mathematical Physics}, volume = {323}, year = {2013}, month = {2013/9/4}, pages = {1121 - 1153}, abstract = { 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]. }, doi = {10.1007/s00220-013-1784-0}, url = {http://arxiv.org/abs/1206.5822v1}, author = {Andrew M. Childs and Debbie Leung and Laura Mancinska and Maris Ozols} } @article {1246, title = {Interpolatability distinguishes LOCC from separable von Neumann measurements}, journal = {Journal of Mathematical Physics}, volume = {54}, year = {2013}, month = {2013/06/25}, pages = {112204}, abstract = { 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. }, doi = {10.1063/1.4830335}, url = {http://arxiv.org/abs/1306.5992v1}, author = {Andrew M. Childs and Debbie Leung and Laura Mancinska and Maris Ozols} } @article {1229, title = {Product Formulas for Exponentials of Commutators}, journal = {Journal of Mathematical Physics}, volume = {54}, year = {2013}, month = {2013/02/07}, pages = {062202}, abstract = { 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. }, doi = {10.1063/1.4811386}, url = {http://arxiv.org/abs/1211.4945v2}, author = {Andrew M. Childs and Nathan Wiebe} } @article {1258, title = {A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates}, year = {2013}, month = {2013/02/28}, abstract = { 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}). }, url = {http://arxiv.org/abs/1302.7316v1}, author = {Andrew M. Childs and Stacey Jeffery and Robin Kothari and Frederic Magniez} } @article {1221, title = {Universal computation by multi-particle quantum walk}, journal = {Science}, volume = {339}, year = {2013}, month = {2013/02/14}, pages = {791 - 794}, abstract = { 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. }, doi = {10.1126/science.1229957}, url = {http://arxiv.org/abs/1205.3782v2}, author = {Andrew M. Childs and David Gosset and Zak Webb} } @article {1227, title = {Hamiltonian Simulation Using Linear Combinations of Unitary Operations}, journal = {Quantum Information and Computation}, volume = {12}, year = {2012}, month = {2012/11/01}, pages = {901-924}, abstract = { 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. }, url = {http://arxiv.org/abs/1202.5822v1}, author = {Andrew M. Childs and Nathan Wiebe} } @article {1228, title = {Levinson{\textquoteright}s theorem for graphs II}, journal = {Journal of Mathematical Physics}, volume = {53}, year = {2012}, month = {2012/11/21}, pages = {102207}, abstract = { We prove Levinson{\textquoteright}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. }, doi = {10.1063/1.4757665}, url = {http://arxiv.org/abs/1203.6557v2}, author = {Andrew M. Childs and David Gosset} } @article {1222, title = {The quantum query complexity of read-many formulas}, journal = {Lecture Notes in Computer Science}, volume = {7501}, year = {2012}, month = {2012/09/10}, pages = {337-348}, abstract = { 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. }, doi = {10.1007/978-3-642-33090-2_30}, url = {http://arxiv.org/abs/1112.0548v1}, author = {Andrew M. Childs and Shelby Kimmel and Robin Kothari} } @article {1225, title = {Levinson{\textquoteright}s theorem for graphs}, journal = {Journal of Mathematical Physics}, volume = {52}, year = {2011}, month = {2011/06/30}, pages = {082102}, abstract = { We prove an analog of Levinson{\textquoteright}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). }, doi = {10.1063/1.3622608}, url = {http://arxiv.org/abs/1103.5077v2}, author = {Andrew M. Childs and DJ Strouse} } @article {1224, title = {Quantum query complexity of minor-closed graph properties}, journal = {Proc. 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics}, volume = {9}, year = {2011}, month = {2011/01/01}, pages = {661-672}, abstract = { 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. }, doi = {10.4230/LIPIcs.STACS.2011.661}, url = {http://arxiv.org/abs/1011.1443v2}, author = {Andrew M. Childs and Robin Kothari} } @article {1242, title = {Characterization of universal two-qubit Hamiltonians}, year = {2010}, month = {2010/04/09}, abstract = { 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. }, url = {http://arxiv.org/abs/1004.1645v2}, author = {Andrew M. Childs and Debbie Leung and Laura Mancinska and Maris Ozols} } @article {1218, title = {Quantum algorithms for algebraic problems}, journal = {Reviews of Modern Physics}, volume = {82}, year = {2010}, month = {2010/1/15}, pages = {1 - 52}, abstract = { 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. }, doi = {10.1103/RevModPhys.82.1}, url = {http://arxiv.org/abs/0812.0380v1}, author = {Andrew M. Childs and Wim van Dam} } @article {1243, title = {Quantum property testing for bounded-degree graphs}, journal = {Proc. RANDOM}, year = {2010}, month = {2010/12/14}, pages = {365-376}, abstract = { 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. }, doi = {10.1007/978-3-642-22935-0_31}, url = {http://arxiv.org/abs/1012.3174v3}, author = {Andris Ambainis and Andrew M. Childs and Yi-Kai Liu} } @article {1206, title = {On the relationship between continuous- and discrete-time quantum walk}, journal = {Communications in Mathematical Physics}, volume = {294}, year = {2010}, month = {2009/10/10}, pages = {581 - 603}, abstract = { 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. }, doi = {10.1007/s00220-009-0930-1}, url = {http://arxiv.org/abs/0810.0312v3}, author = {Andrew M. Childs} } @article {1223, title = {Simulating sparse Hamiltonians with star decompositions}, year = {2010}, month = {2010/03/18}, abstract = { 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. }, doi = {10.1007/978-3-642-18073-6_8}, url = {http://arxiv.org/abs/1003.3683v2}, author = {Andrew M. Childs and Robin Kothari} } @article {1220, title = {Black-box Hamiltonian simulation and unitary implementation}, year = {2009}, month = {2009/10/22}, abstract = { 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. }, url = {http://arxiv.org/abs/0910.4157v4}, author = {Dominic W. Berry and Andrew M. Childs} } @article {1254, title = {Discrete-query quantum algorithm for NAND trees}, journal = {Theory of Computing}, volume = {5}, year = {2009}, month = {2009/07/01}, pages = {119 - 123}, abstract = { Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0. }, doi = {10.4086/toc.2009.v005a005}, url = {http://arxiv.org/abs/quant-ph/0702160v1}, author = {Andrew M. Childs and Richard Cleve and Stephen P. Jordan and David Yeung} } @article {1219, title = {Limitations on the simulation of non-sparse Hamiltonians}, year = {2009}, month = {2009/08/31}, abstract = { 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. }, url = {http://arxiv.org/abs/0908.4398v2}, author = {Andrew M. Childs and Robin Kothari} } @article {1256, title = {The quantum query complexity of certification}, year = {2009}, month = {2009/03/06}, abstract = { 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. }, url = {http://arxiv.org/abs/0903.1291v2}, author = {Andris Ambainis and Andrew M. Childs and Fran{\c c}ois Le Gall and Seiichiro Tani} } @article {1205, title = {Universal computation by quantum walk}, journal = {Physical Review Letters}, volume = {102}, year = {2009}, month = {2009/5/4}, abstract = { 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. }, doi = {10.1103/PhysRevLett.102.180501}, url = {http://arxiv.org/abs/0806.1972v1}, author = {Andrew M. Childs} } @article {1255, title = {Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer }, year = {2007}, month = {2007/03/02}, abstract = { 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 {\textquoteleft}{\textquoteleft}approximately balanced,{\textquoteright}{\textquoteright} 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. }, url = {http://arxiv.org/abs/quant-ph/0703015v3}, author = {Andrew M. Childs and Ben W. Reichardt and Robert Spalek and Shengyu Zhang} } @article {1253, title = {Improved quantum algorithms for the ordered search problem via semidefinite programming }, journal = {Physical Review A}, volume = {75}, year = {2007}, month = {2007/3/26}, abstract = { 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. }, doi = {10.1103/PhysRevA.75.032335}, url = {http://arxiv.org/abs/quant-ph/0608161v1}, author = {Andrew M. Childs and Andrew J. Landahl and Pablo A. Parrilo} } @article {1214, title = {The limitations of nice mutually unbiased bases}, journal = {Journal of Algebraic Combinatorics}, volume = {25}, year = {2007}, month = {2006/7/11}, pages = {111 - 123}, abstract = { 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. }, doi = {10.1007/s10801-006-0002-y}, url = {http://arxiv.org/abs/quant-ph/0412066v1}, author = {Michael Aschbacher and Andrew M. Childs and Pawel Wocjan} } @article {1217, title = {Optimal quantum adversary lower bounds for ordered search}, year = {2007}, month = {2007/08/24}, abstract = { 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. }, doi = {10.1007/978-3-540-70575-8_71}, url = {http://arxiv.org/abs/0708.3396v1}, author = {Andrew M. Childs and Troy Lee} } @article {1257, title = {Quantum algorithms for hidden nonlinear structures}, year = {2007}, month = {2007/05/21}, abstract = { 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{\textquoteright}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. }, doi = {10.1109/FOCS.2007.18}, url = {http://arxiv.org/abs/0705.2784v1}, author = {Andrew M. Childs and Leonard J. Schulman and Umesh V. Vazirani} } @article {1252, title = {Two-way quantum communication channels}, journal = {International Journal of Quantum Information}, volume = {04}, year = {2006}, month = {2006/02/01}, pages = {63 - 83}, abstract = { 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. }, doi = {10.1142/S0219749906001621}, url = {http://arxiv.org/abs/quant-ph/0506039v1}, author = {Andrew M. Childs and Debbie W. Leung and Hoi-Kwong Lo} } @article {1241, title = {Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem }, year = {2006}, month = {2006/09/14}, abstract = { 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. }, doi = {10.1007/978-3-540-70918-3_51}, url = {http://arxiv.org/abs/quant-ph/0609110v1}, author = {Andrew M. Childs and Aram W. Harrow and Pawel Wocjan} } @article {1240, title = {From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups }, year = {2005}, month = {2005/04/11}, abstract = { 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. }, doi = {10.1109/SFCS.2005.38}, url = {http://arxiv.org/abs/quant-ph/0504083v2}, author = {Dave Bacon and Andrew M. Childs and Wim van Dam} } @article {1239, title = {Optimal measurements for the dihedral hidden subgroup problem}, year = {2005}, month = {2005/01/10}, abstract = { 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. }, url = {http://arxiv.org/abs/quant-ph/0501044v2}, author = {Dave Bacon and Andrew M. Childs and Wim van Dam} } @article {1215, title = {Quantum algorithm for a generalized hidden shift problem}, year = {2005}, month = {2005/07/19}, abstract = { 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{\textquoteright}s (classical) algorithm for integer programming as a subroutine. }, url = {http://arxiv.org/abs/quant-ph/0507190v1}, author = {Andrew M. Childs and Wim van Dam} } @article {1216, title = {On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems }, year = {2005}, month = {2005/10/25}, abstract = { 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. }, url = {http://arxiv.org/abs/quant-ph/0510185v1}, author = {Andrew M. Childs and Pawel Wocjan} } @article {1251, title = {Unified derivations of measurement-based schemes for quantum computation}, journal = {Physical Review A}, volume = {71}, year = {2005}, month = {2005/3/17}, abstract = { 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. }, doi = {10.1103/PhysRevA.71.032318}, url = {http://arxiv.org/abs/quant-ph/0404132v2}, author = {Andrew M. Childs and Debbie W. Leung and Michael A. Nielsen} } @article {1238, title = {Reversible simulation of bipartite product Hamiltonians}, journal = {IEEE Transactions on Information Theory}, volume = {50}, year = {2004}, month = {2004/06/01}, pages = {1189 - 1197}, abstract = { 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. }, doi = {10.1109/TIT.2004.828069}, url = {http://arxiv.org/abs/quant-ph/0303097v1}, author = {Andrew M. Childs and Debbie W. Leung and Guifre Vidal} } @article {1213, title = {Spatial search and the Dirac equation}, journal = {Physical Review A}, volume = {70}, year = {2004}, month = {2004/10/19}, abstract = { 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. }, doi = {10.1103/PhysRevA.70.042312}, url = {http://arxiv.org/abs/quant-ph/0405120v1}, author = {Andrew M. Childs and Jeffrey Goldstone} } @article {1211, title = {Spatial search by quantum walk}, journal = {Physical Review A}, volume = {70}, year = {2004}, month = {2004/8/23}, abstract = { Grover{\textquoteright}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. }, doi = {10.1103/PhysRevA.70.022314}, url = {http://arxiv.org/abs/quant-ph/0306054v2}, author = {Andrew M. Childs and Jeffrey Goldstone} } @article {1250, title = {Lower bounds on the complexity of simulating quantum gates}, journal = {Physical Review A}, volume = {68}, year = {2003}, month = {2003/11/18}, abstract = { 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. }, doi = {10.1103/PhysRevA.68.052311}, url = {http://arxiv.org/abs/quant-ph/0307190v1}, author = {Andrew M. Childs and Henry L. Haselgrove and Michael A. Nielsen} } @article {1212, title = {Quantum algorithms for subset finding}, year = {2003}, month = {2003/11/06}, abstract = { 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. }, url = {http://arxiv.org/abs/quant-ph/0311038v2}, author = {Andrew M. Childs and Jason M. Eisenberg} } @article {1210, title = {Asymptotic entanglement capacity of the Ising and anisotropic Heisenberg interactions }, year = {2002}, month = {2002/07/10}, abstract = { 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. }, url = {http://arxiv.org/abs/quant-ph/0207052v2}, author = {A. M. Childs and D. W. Leung and F. Verstraete and G. Vidal} } @article {1263, title = {Exponential algorithmic speedup by quantum walk}, year = {2002}, month = {2002/09/24}, abstract = { 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. }, doi = {10.1145/780542.780552}, url = {http://arxiv.org/abs/quant-ph/0209131v2}, author = {Andrew M. Childs and Richard Cleve and Enrico Deotto and Edward Farhi and Sam Gutmann and Daniel A. Spielman} } @article {1262, title = {Quantum search by measurement}, journal = {Physical Review A}, volume = {66}, year = {2002}, month = {2002/9/23}, abstract = { 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{\textquoteright}s unstructured search problem with only two measurements. Finally, we discuss some similarities and differences between the adiabatic and measurement algorithms. }, doi = {10.1103/PhysRevA.66.032314}, url = {http://arxiv.org/abs/quant-ph/0204013v1}, author = {Andrew M. Childs and Enrico Deotto and Edward Farhi and Jeffrey Goldstone and Sam Gutmann and Andrew J. Landahl} } @article {1261, title = {Universal simulation of Hamiltonian dynamics for qudits}, journal = {Physical Review A}, volume = {66}, year = {2002}, month = {2002/8/30}, abstract = { 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. }, doi = {10.1103/PhysRevA.66.022317}, url = {http://arxiv.org/abs/quant-ph/0109064v2}, author = {Michael A. Nielsen and Michael J. Bremner and Jennifer L. Dodd and Andrew M. Childs and Christopher M. Dawson} } @article {1248, title = {Exact sampling from non-attractive distributions using summary states}, journal = {Physical Review E}, volume = {63}, year = {2001}, month = {2001/2/22}, abstract = { Propp and Wilson{\textquoteright}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. }, doi = {10.1103/PhysRevE.63.036113}, url = {http://arxiv.org/abs/cond-mat/0005132v1}, author = {Andrew M. Childs and Ryan B. Patterson and David J. C. MacKay} } @article {1208, title = {An example of the difference between quantum and classical random walks}, journal = {Quantum Information Processing}, volume = {1}, year = {2001}, month = {2002/04/01}, pages = {35 - 43}, abstract = { 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. }, doi = {10.1023/A:1019609420309}, url = {http://arxiv.org/abs/quant-ph/0103020v1}, author = {Andrew M. Childs and Edward Farhi and Sam Gutmann} } @article {1249, title = {Realization of quantum process tomography in NMR}, journal = {Physical Review A}, volume = {64}, year = {2001}, month = {2001/6/13}, abstract = { 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. }, doi = {10.1103/PhysRevA.64.012314}, url = {http://arxiv.org/abs/quant-ph/0012032v1}, author = {Andrew M. Childs and Isaac L. Chuang and Debbie W. Leung} } @article {1209, title = {Robustness of adiabatic quantum computation}, journal = {Physical Review A}, volume = {65}, year = {2001}, month = {2001/12/14}, abstract = { 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. }, doi = {10.1103/PhysRevA.65.012322}, url = {http://arxiv.org/abs/quant-ph/0108048v1}, author = {Andrew M. Childs and Edward Farhi and John Preskill} } @article {1204, title = {Secure assisted quantum computation}, year = {2001}, month = {2001/11/07}, abstract = { 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. }, url = {http://arxiv.org/abs/quant-ph/0111046v2}, author = {Andrew M. Childs} } @article {1260, title = {Universal simulation of Markovian quantum dynamics}, journal = {Physical Review A}, volume = {64}, year = {2001}, month = {2001/11/9}, abstract = { 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. }, doi = {10.1103/PhysRevA.64.062302}, url = {http://arxiv.org/abs/quant-ph/0008070v2}, author = {Dave Bacon and Andrew M. Childs and Isaac L. Chuang and Julia Kempe and Debbie W. Leung and Xinlan Zhou} } @article {1237, title = {Finding cliques by quantum adiabatic evolution}, year = {2000}, month = {2000/12/19}, abstract = { 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. }, url = {http://arxiv.org/abs/quant-ph/0012104v1}, author = {Andrew M. Childs and Edward Farhi and Jeffrey Goldstone and Sam Gutmann} } @article {1236, title = {Quantum information and precision measurement}, journal = {Journal of Modern Optics}, volume = {47}, year = {2000}, month = {1999/04/07}, pages = {155 - 176}, abstract = { 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. }, doi = {10.1080/09500340008244034}, url = {http://arxiv.org/abs/quant-ph/9904021v2}, author = {Andrew M. Childs and John Preskill and Joseph Renes} } @article {1207, title = {Universal quantum computation with two-level trapped ions}, journal = {Physical Review A}, volume = {63}, year = {2000}, month = {2000/12/11}, abstract = { 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. }, doi = {10.1103/PhysRevA.63.012306}, url = {http://arxiv.org/abs/quant-ph/0008065v1}, author = {Andrew M. Childs and Isaac L. Chuang} }