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.

1 aChilds, Andrew, M.1 aSchoute, Eddie1 aUnsal, Cem, M. uhttps://arxiv.org/abs/1902.0910201743nas a2200205 4500008004100000245007000041210006900111260001500180490000600195520112800201100002101329700002001350700001301370700002401383700002201407700002301429700002301452700002501475856003701500 2019 eng d00aLocality and digital quantum simulation of power-law interactions0 aLocality and digital quantum simulation of powerlaw interactions c07/10/20190 v93 aThe 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).

1 aTran, Minh, Cong1 aGuo, Andrew, Y.1 aSu, Yuan1 aGarrison, James, R.1 aEldredge, Zachary1 aFoss-Feig, Michael1 aChilds, Andrew, M.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1808.0522501443nas a2200109 4500008004100000245005800041210005800099520110300157100002301260700001301283856003701296 2019 eng d00aNearly optimal lattice simulation by product formulas0 aNearly optimal lattice simulation by product formulas3 aProduct 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.

1 aChilds, Andrew, M.1 aSu, Yuan uhttps://arxiv.org/abs/1901.0056401220nas a2200109 4500008004100000245005600041210005600097520087900153100002301032700001801055856003701073 2019 eng d00aQuantum spectral methods for differential equations0 aQuantum spectral methods for differential equations3 aRecently 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/ε)).

1 aChilds, Andrew, M.1 aLiu, Jin-Peng uhttps://arxiv.org/abs/1901.0096101754nas a2200157 4500008004100000245006700041210006600108260001500174520126400189100002001453700001901473700002301492700002501515700001901540856003701559 2019 eng d00aSignaling and Scrambling with Strongly Long-Range Interactions0 aSignaling and Scrambling with Strongly LongRange Interactions c06/06/20193 aStrongly 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.

1 aGuo, Andrew, Y.1 aTran, Minh, C.1 aChilds, Andrew, M.1 aGorshkov, Alexey, V.1 aGong, Zhe-Xuan uhttps://arxiv.org/abs/1906.0266201651nas a2200157 4500008004100000245006300041210006100104260001500165520118500180100002301365700002301388700001301411700001401424700001801438856003701456 2019 eng d00aTime-dependent Hamiltonian simulation with L1-norm scaling0 aTimedependent Hamiltonian simulation with L1norm scaling c06/17/20193 aThe 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.

1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aSu, Yuan1 aWang, Xin1 aWiebe, Nathan uhttps://arxiv.org/abs/1906.0711501295nas a2200169 4500008004100000245008000041210006900121260001500190490000600205520078500211100001800996700001901014700001301033700002301046700001901069856003701088 2018 eng d00aAutomated optimization of large quantum circuits with continuous parameters0 aAutomated optimization of large quantum circuits with continuous c2017/10/190 v43 aWe 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.

1 aNam, Yunseong1 aRoss, Neil, J.1 aSu, Yuan1 aChilds, Andrew, M.1 aMaslov, Dmitri uhttps://arxiv.org/abs/1710.0734501266nas a2200133 4500008004100000245004700041210004700088260001500135520088800150100002301038700002101061700001301082856003701095 2018 eng d00aFaster quantum simulation by randomization0 aFaster quantum simulation by randomization c2018/05/223 aProduct 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.

1 aChilds, Andrew, M.1 aOstrander, Aaron1 aSu, Yuan uhttps://arxiv.org/abs/1805.0838501497nas a2200145 4500008004100000245006400041210006400105260001500169490000800184520103000192100001801222700002301240700001901263856006901282 2018 eng d00aQuantum algorithm for multivariate polynomial interpolation0 aQuantum algorithm for multivariate polynomial interpolation c2018/01/170 v4743 aHow 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.

1 aChen, Jianxin1 aChilds, Andrew, M.1 aHung, Shih-Han uhttp://rspa.royalsocietypublishing.org/content/474/2209/2017048001128nas a2200133 4500008004100000245006400041210006400105520070600169100002700875700002300902700001700925700001500942856003700957 2018 eng d00aQuantum algorithms and lower bounds for convex optimization0 aQuantum algorithms and lower bounds for convex optimization3 aWhile 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.

1 aChakrabarti, Shouvanik1 aChilds, Andrew, M.1 aLi, Tongyang1 aWu, Xiaodi uhttps://arxiv.org/abs/1809.0173101648nas a2200169 4500008004100000245006100041210006100102300001400163490000900177520116300186100002301349700001901372700001801391700001901409700001301428856003701441 2018 eng d00aToward the first quantum simulation with quantum speedup0 aToward the first quantum simulation with quantum speedup a9456-94610 v115 3 aWith 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.

1 aChilds, Andrew, M.1 aMaslov, Dmitri1 aNam, Yunseong1 aRoss, Neil, J.1 aSu, Yuan uhttps://arxiv.org/abs/1711.1098001386nas a2200145 4500008004100000245006200041210006200103260001500165300001200180490000700192520096400199100002301163700001701186856003701203 2017 eng d00aEfficient simulation of sparse Markovian quantum dynamics0 aEfficient simulation of sparse Markovian quantum dynamics c2017/09/01 a901-9470 v173 aQuantum 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.

1 aChilds, Andrew, M.1 aLi, Tongyang uhttps://arxiv.org/abs/1611.0554301429nas a2200169 4500008004100000245010800041210006900149260001500218300001400233490000800247520088200255100002301137700002301160700002101183700001801204856003701222 2017 eng d00aQuantum algorithm for linear differential equations with exponentially improved dependence on precision0 aQuantum algorithm for linear differential equations with exponen c2017/12/01 a1057-10810 v3563 aWe 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.

1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aOstrander, Aaron1 aWang, Guoming uhttps://arxiv.org/abs/1701.0368401362nas a2200157 4500008004100000245010600041210006900147260001500216300001400231490000700245520083800252100002301090700001901113700002301132856004901155 2017 eng d00aQuantum algorithm for systems of linear equations with exponentially improved dependence on precision0 aQuantum algorithm for systems of linear equations with exponenti c2017/12/21 a1920-19500 v463 aHarrow, 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.

1 aChilds, Andrew, M.1 aKothari, Robin1 aSomma, Rolando, D. uhttp://epubs.siam.org/doi/10.1137/16M108707200953nas a2200157 4500008004100000245006400041210006400105260001500169300000900184490000700193520050200200100002300702700001800725700001400743856003800757 2016 eng d00aComplexity of the XY antiferromagnet at fixed magnetization0 aComplexity of the XY antiferromagnet at fixed magnetization c2016/01/01 a1-180 v163 a 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. 1 aChilds, Andrew, M.1 aGosset, David1 aWebb, Zak uhttp://arxiv.org/abs/1503.07083v101532nas a2200193 4500008004100000020002200041022001400063245005900077210005900136260001500195300001600210490000700226520098400233100002301217700001701240700001901257700002601276856003601302 2016 eng d a978-3-95977-013-2 a1868-896900aOptimal quantum algorithm for polynomial interpolation0 aOptimal quantum algorithm for polynomial interpolation c2016/03/01 a16:1--16:130 v553 aWe 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.

1 aChilds, Andrew, M.1 avan Dam, Wim1 aHung, Shih-Han1 aShparlinski, Igor, E. uhttp://arxiv.org/abs/1509.0927101395nas a2200145 4500008004100000245008900041210006900130260001500199300001100214490000700225520094000232100002301172700001801195856003601213 2016 eng d00aOptimal state discrimination and unstructured search in nonlinear quantum mechanics0 aOptimal state discrimination and unstructured search in nonlinea c2016/02/11 a0223140 v933 a 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. 1 aChilds, Andrew, M.1 aYoung, Joshua uhttp://arxiv.org/abs/1507.0633401453nas a2200145 4500008004100000245007600041210006900117260001500186300001200201520099300213100002301206700002301229700001901252856003601271 2015 eng d00aHamiltonian simulation with nearly optimal dependence on all parameters0 aHamiltonian simulation with nearly optimal dependence on all par c2015/01/08 a792-8093 a 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$. 1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aKothari, Robin uhttp://arxiv.org/abs/1501.0171500877nas a2200181 4500008004100000245002200041210002200063260001500085300001200100490000700112520044800119100002300567700001800590700001800608700001800626700001400644856003700658 2015 eng d00aMomentum switches0 aMomentum switches c2015/05/01 a601-6210 v153 a 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. 1 aChilds, Andrew, M.1 aGosset, David1 aNagaj, Daniel1 aRaha, Mouktik1 aWebb, Zak uhttp://arxiv.org/abs/1406.4510v101120nas a2200181 4500008004100000245006700041210006700108260001500175300001100190490000800201520058500209100002300794700002300817700001900840700001900859700002300878856003700901 2015 eng d00aSimulating Hamiltonian dynamics with a truncated Taylor series0 aSimulating Hamiltonian dynamics with a truncated Taylor series c2015/03/03 a0905020 v1143 a 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. 1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aCleve, Richard1 aKothari, Robin1 aSomma, Rolando, D. uhttp://arxiv.org/abs/1412.4687v101367nas a2200157 4500008004100000245004300041210003700084260001500121300001200136490000900148520096000157100002301117700001801140700001401158856003701172 2014 eng d00aThe Bose-Hubbard model is QMA-complete0 aBoseHubbard model is QMAcomplete c2014/07/08 a308-3190 v85723 a 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. 1 aChilds, Andrew, M.1 aGosset, David1 aWebb, Zak uhttp://arxiv.org/abs/1311.3297v101064nas a2200145 4500008004100000245008600041210006900127260001500196300001200211490000700223520060700230100002100837700002300858856003700881 2014 eng d00aThe computational power of matchgates and the XY interaction on arbitrary graphs0 acomputational power of matchgates and the XY interaction on arbi c2014/09/01 a901-9160 v143 a 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. 1 aBrod, Daniel, J.1 aChilds, Andrew, M. uhttp://arxiv.org/abs/1308.1463v101598nas a2200157 4500008004100000245007300041210006900114260001500183300001100198490000600209520112600215100002301341700001501364700002401379856003701403 2014 eng d00aConstructing elliptic curve isogenies in quantum subexponential time0 aConstructing elliptic curve isogenies in quantum subexponential c2014/01/01 a1 - 290 v83 a 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. 1 aChilds, Andrew, M.1 aJao, David1 aSoukharev, Vladimir uhttp://arxiv.org/abs/1012.4019v202001nas a2200181 4500008004100000020002200041245007600063210006900139260001500208300001200223520144000235100002301675700002301698700001901721700001901740700002301759856003701782 2014 eng d a978-1-4503-2710-700aExponential improvement in precision for simulating sparse Hamiltonians0 aExponential improvement in precision for simulating sparse Hamil c2014/05/31 a283-2923 a 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. 1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aCleve, Richard1 aKothari, Robin1 aSomma, Rolando, D. uhttp://arxiv.org/abs/1312.1414v201152nas a2200133 4500008004100000245006100041210006100102260001400163490000600177520075500183100002300938700002000961856003700981 2014 eng d00aQuantum computation of discrete logarithms in semigroups0 aQuantum computation of discrete logarithms in semigroups c2014/01/10 v83 a 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. 1 aChilds, Andrew, M.1 aIvanyos, Gábor uhttp://arxiv.org/abs/1310.6238v201146nas a2200133 4500008004100000245007200041210006900113260001400182490000700196520073500203100002300938700001400961856003700975 2014 eng d00aSpatial search by continuous-time quantum walks on crystal lattices0 aSpatial search by continuoustime quantum walks on crystal lattic c2014/5/300 v893 a 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. 1 aChilds, Andrew, M.1 aGe, Yimin uhttp://arxiv.org/abs/1403.2676v201395nas a2200169 4500008004100000245006500041210006500106260001500171300001000186490000700196520090400203100002301107700001901130700001701149700002201166856003701188 2013 eng d00aEasy and hard functions for the Boolean hidden shift problem0 aEasy and hard functions for the Boolean hidden shift problem c2013/04/16 a50-790 v223 a 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. 1 aChilds, Andrew, M.1 aKothari, Robin1 aOzols, Maris1 aRoetteler, Martin uhttp://arxiv.org/abs/1304.4642v101336nas a2200169 4500008004100000245006500041210006300106260001300169300001600182490000800198520084400206100002301050700001801073700002101091700001701112856003701129 2013 eng d00aA framework for bounding nonlocality of state discrimination0 aframework for bounding nonlocality of state discrimination c2013/9/4 a1121 - 11530 v3233 a 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]. 1 aChilds, Andrew, M.1 aLeung, Debbie1 aMancinska, Laura1 aOzols, Maris uhttp://arxiv.org/abs/1206.5822v100982nas a2200169 4500008004100000245008200041210006900123260001500192300001100207490000700218520047100225100002300696700001800719700002100737700001700758856003700775 2013 eng d00aInterpolatability distinguishes LOCC from separable von Neumann measurements0 aInterpolatability distinguishes LOCC from separable von Neumann c2013/06/25 a1122040 v543 a 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. 1 aChilds, Andrew, M.1 aLeung, Debbie1 aMancinska, Laura1 aOzols, Maris uhttp://arxiv.org/abs/1306.5992v101289nas a2200145 4500008004100000245005300041210005300094260001500147300001100162490000700173520088500180100002301065700001801088856003701106 2013 eng d00aProduct Formulas for Exponentials of Commutators0 aProduct Formulas for Exponentials of Commutators c2013/02/07 a0622020 v543 a 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. 1 aChilds, Andrew, M.1 aWiebe, Nathan uhttp://arxiv.org/abs/1211.4945v200867nas a2200145 4500008004100000245007400041210006900115260001500184520040100199100002300600700002000623700001900643700002200662856003700684 2013 eng d00aA Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates0 aTimeEfficient Quantum Walk for 3Distinctness Using Nested Update c2013/02/283 a 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}). 1 aChilds, Andrew, M.1 aJeffery, Stacey1 aKothari, Robin1 aMagniez, Frederic uhttp://arxiv.org/abs/1302.7316v101608nas a2200157 4500008004100000245005700041210005600098260001500154300001400169490000800183520116700191100002301358700001801381700001401399856003701413 2013 eng d00aUniversal computation by multi-particle quantum walk0 aUniversal computation by multiparticle quantum walk c2013/02/14 a791 - 7940 v3393 a 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. 1 aChilds, Andrew, M.1 aGosset, David1 aWebb, Zak uhttp://arxiv.org/abs/1205.3782v201023nas a2200145 4500008004100000245007500041210006900116260001500185300001200200490000700212520058000219100002300799700001800822856003700840 2012 eng d00aHamiltonian Simulation Using Linear Combinations of Unitary Operations0 aHamiltonian Simulation Using Linear Combinations of Unitary Oper c2012/11/01 a901-9240 v123 a 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. 1 aChilds, Andrew, M.1 aWiebe, Nathan uhttp://arxiv.org/abs/1202.5822v100869nas a2200145 4500008004100000245003700041210003600078260001500114300001100129490000700140520049800147100002300645700001800668856003700686 2012 eng d00aLevinson's theorem for graphs II0 aLevinsons theorem for graphs II c2012/11/21 a1022070 v533 a 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. 1 aChilds, Andrew, M.1 aGosset, David uhttp://arxiv.org/abs/1203.6557v201823nas a2200157 4500008004100000245005500041210005000096260001500146300001200161490000900173520138500182100002301567700001901590700001901609856003701628 2012 eng d00aThe quantum query complexity of read-many formulas0 aquantum query complexity of readmany formulas c2012/09/10 a337-3480 v75013 a 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. 1 aChilds, Andrew, M.1 aKimmel, Shelby1 aKothari, Robin uhttp://arxiv.org/abs/1112.0548v100769nas a2200145 4500008004100000245003400041210003300075260001500108300001100123490000700134520040600141100002300547700001600570856003700586 2011 eng d00aLevinson's theorem for graphs0 aLevinsons theorem for graphs c2011/06/30 a0821020 v523 a 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). 1 aChilds, Andrew, M.1 aStrouse, DJ uhttp://arxiv.org/abs/1103.5077v201380nas a2200145 4500008004100000245006200041210006100103260001500164300001200179490000600191520095800197100002301155700001901178856003701197 2011 eng d00aQuantum query complexity of minor-closed graph properties0 aQuantum query complexity of minorclosed graph properties c2011/01/01 a661-6720 v93 a 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. 1 aChilds, Andrew, M.1 aKothari, Robin uhttp://arxiv.org/abs/1011.1443v201458nas a2200145 4500008004100000245005700041210005600098260001500154520102700169100002301196700001801219700002101237700001701258856003701275 2010 eng d00aCharacterization of universal two-qubit Hamiltonians0 aCharacterization of universal twoqubit Hamiltonians c2010/04/093 a 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. 1 aChilds, Andrew, M.1 aLeung, Debbie1 aMancinska, Laura1 aOzols, Maris uhttp://arxiv.org/abs/1004.1645v201122nas a2200145 4500008004100000245004600041210004600087260001400133300001100147490000700158520073400165100002300899700001700922856003700939 2010 eng d00aQuantum algorithms for algebraic problems0 aQuantum algorithms for algebraic problems c2010/1/15 a1 - 520 v823 a 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. 1 aChilds, Andrew, M.1 avan Dam, Wim uhttp://arxiv.org/abs/0812.0380v101146nas a2200145 4500008004100000245005500041210005400096260001500150300001200165520072600177100002100903700002300924700001600947856003700963 2010 eng d00aQuantum property testing for bounded-degree graphs0 aQuantum property testing for boundeddegree graphs c2010/12/14 a365-3763 a 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. 1 aAmbainis, Andris1 aChilds, Andrew, M.1 aLiu, Yi-Kai uhttp://arxiv.org/abs/1012.3174v301937nas a2200133 4500008004100000245007500041210006600116260001500182300001400197490000800211520152400219100002301743856003701766 2010 eng d00aOn the relationship between continuous- and discrete-time quantum walk0 arelationship between continuous and discretetime quantum walk c2009/10/10 a581 - 6030 v2943 a 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. 1 aChilds, Andrew, M. uhttp://arxiv.org/abs/0810.0312v301041nas a2200121 4500008004100000245006000041210006000101260001500161520066400176100002300840700001900863856003700882 2010 eng d00aSimulating sparse Hamiltonians with star decompositions0 aSimulating sparse Hamiltonians with star decompositions c2010/03/183 a 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. 1 aChilds, Andrew, M.1 aKothari, Robin uhttp://arxiv.org/abs/1003.3683v201436nas a2200121 4500008004100000245006400041210006300105260001500168520104800183100002301231700002301254856003701277 2009 eng d00aBlack-box Hamiltonian simulation and unitary implementation0 aBlackbox Hamiltonian simulation and unitary implementation c2009/10/223 a 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. 1 aBerry, Dominic, W.1 aChilds, Andrew, M. uhttp://arxiv.org/abs/0910.4157v400832nas a2200169 4500008004100000245005200041210005100093260001500144300001400159490000600173520035600179100002300535700001900558700002400577700001700601856004400618 2009 eng d00aDiscrete-query quantum algorithm for NAND trees0 aDiscretequery quantum algorithm for NAND trees c2009/07/01 a119 - 1230 v53 a Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0. 1 aChilds, Andrew, M.1 aCleve, Richard1 aJordan, Stephen, P.1 aYeung, David uhttp://arxiv.org/abs/quant-ph/0702160v101322nas a2200121 4500008004100000245006100041210006000102260001500162520094400177100002301121700001901144856003701163 2009 eng d00aLimitations on the simulation of non-sparse Hamiltonians0 aLimitations on the simulation of nonsparse Hamiltonians c2009/08/313 a 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. 1 aChilds, Andrew, M.1 aKothari, Robin uhttp://arxiv.org/abs/0908.4398v200937nas a2200145 4500008004100000245005000041210004600091260001500137520051500152100002100667700002300688700002300711700002000734856003700754 2009 eng d00aThe quantum query complexity of certification0 aquantum query complexity of certification c2009/03/063 a 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. 1 aAmbainis, Andris1 aChilds, Andrew, M.1 aLe Gall, François1 aTani, Seiichiro uhttp://arxiv.org/abs/0903.1291v200931nas a2200121 4500008004100000245004200041210004200083260001300125490000800138520060300146100002300749856003700772 2009 eng d00aUniversal computation by quantum walk0 aUniversal computation by quantum walk c2009/5/40 v1023 a 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. 1 aChilds, Andrew, M. uhttp://arxiv.org/abs/0806.1972v100984nas a2200145 4500008004100000245009600041210006900137260001500206520048900221100002300710700002300733700001900756700001900775856004400794 2007 eng d00aEvery NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer 0 aEvery NAND formula of size N can be evaluated in time N 12o1 on c2007/03/023 a 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. 1 aChilds, Andrew, M.1 aReichardt, Ben, W.1 aSpalek, Robert1 aZhang, Shengyu uhttp://arxiv.org/abs/quant-ph/0703015v301273nas a2200145 4500008004100000245009500041210006900136260001400205490000700219520078700226100002301013700002401036700002301060856004401083 2007 eng d00aImproved quantum algorithms for the ordered search problem via semidefinite programming 0 aImproved quantum algorithms for the ordered search problem via s c2007/3/260 v753 a 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. 1 aChilds, Andrew, M.1 aLandahl, Andrew, J.1 aParrilo, Pablo, A. uhttp://arxiv.org/abs/quant-ph/0608161v101144nas a2200157 4500008004100000245005200041210004800093260001400141300001400155490000700169520070100176100002400877700002300901700001800924856004400942 2007 eng d00aThe limitations of nice mutually unbiased bases0 alimitations of nice mutually unbiased bases c2006/7/11 a111 - 1230 v253 a 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. 1 aAschbacher, Michael1 aChilds, Andrew, M.1 aWocjan, Pawel uhttp://arxiv.org/abs/quant-ph/0412066v101045nas a2200121 4500008004100000245006200041210006200103260001500165520066900180100002300849700001400872856003700886 2007 eng d00aOptimal quantum adversary lower bounds for ordered search0 aOptimal quantum adversary lower bounds for ordered search c2007/08/243 a 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. 1 aChilds, Andrew, M.1 aLee, Troy uhttp://arxiv.org/abs/0708.3396v100989nas a2200133 4500008004100000245005500041210005500096260001500151520057900166100002300745700002600768700002400794856003700818 2007 eng d00aQuantum algorithms for hidden nonlinear structures0 aQuantum algorithms for hidden nonlinear structures c2007/05/213 a 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. 1 aChilds, Andrew, M.1 aSchulman, Leonard, J.1 aVazirani, Umesh, V. uhttp://arxiv.org/abs/0705.2784v101338nas a2200157 4500008004100000245004300041210004200084260001500126300001200141490000700153520091300160100002301073700002201096700001801118856004401136 2006 eng d00aTwo-way quantum communication channels0 aTwoway quantum communication channels c2006/02/01 a63 - 830 v043 a 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. 1 aChilds, Andrew, M.1 aLeung, Debbie, W.1 aLo, Hoi-Kwong uhttp://arxiv.org/abs/quant-ph/0506039v101297nas a2200133 4500008004100000245009900041210006900140260001500209520083300224100002301057700002101080700001801101856004401119 2006 eng d00aWeak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem 0 aWeak FourierSchur sampling the hidden subgroup problem and the q c2006/09/143 a 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. 1 aChilds, Andrew, M.1 aHarrow, Aram, W.1 aWocjan, Pawel uhttp://arxiv.org/abs/quant-ph/0609110v101370nas a2200133 4500008004100000245012700041210006900168260001500237520088400252100001601136700002301152700001701175856004401192 2005 eng d00aFrom optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups 0 aFrom optimal measurement to efficient quantum algorithms for the c2005/04/113 a 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. 1 aBacon, Dave1 aChilds, Andrew, M.1 avan Dam, Wim uhttp://arxiv.org/abs/quant-ph/0504083v201943nas a2200133 4500008004100000245006600041210006600107260001500173520152100188100001601709700002301725700001701748856004401765 2005 eng d00aOptimal measurements for the dihedral hidden subgroup problem0 aOptimal measurements for the dihedral hidden subgroup problem c2005/01/103 a 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. 1 aBacon, Dave1 aChilds, Andrew, M.1 avan Dam, Wim uhttp://arxiv.org/abs/quant-ph/0501044v201092nas a2200121 4500008004100000245006100041210006100102260001500163520070800178100002300886700001700909856004400926 2005 eng d00aQuantum algorithm for a generalized hidden shift problem0 aQuantum algorithm for a generalized hidden shift problem c2005/07/193 a 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. 1 aChilds, Andrew, M.1 avan Dam, Wim uhttp://arxiv.org/abs/quant-ph/0507190v101105nas a2200121 4500008004100000245009900041210006900140260001500209520067400224100002300898700001800921856004400939 2005 eng d00aOn the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems 0 aquantum hardness of solving isomorphism problems as nonabelian h c2005/10/253 a 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. 1 aChilds, Andrew, M.1 aWocjan, Pawel uhttp://arxiv.org/abs/quant-ph/0510185v101341nas a2200145 4500008004100000245007700041210006900118260001400187490000700201520087300208100002301081700002201104700002501126856004401151 2005 eng d00aUnified derivations of measurement-based schemes for quantum computation0 aUnified derivations of measurementbased schemes for quantum comp c2005/3/170 v713 a 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. 1 aChilds, Andrew, M.1 aLeung, Debbie, W.1 aNielsen, Michael, A. uhttp://arxiv.org/abs/quant-ph/0404132v201270nas a2200157 4500008004100000245006000041210006000101260001500161300001600176490000700192520080600199100002301005700002201028700001801050856004401068 2004 eng d00aReversible simulation of bipartite product Hamiltonians0 aReversible simulation of bipartite product Hamiltonians c2004/06/01 a1189 - 11970 v503 a 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. 1 aChilds, Andrew, M.1 aLeung, Debbie, W.1 aVidal, Guifre uhttp://arxiv.org/abs/quant-ph/0303097v100967nas a2200133 4500008004100000245004200041210004200083260001500125490000700140520059600147100002300743700002300766856004400789 2004 eng d00aSpatial search and the Dirac equation0 aSpatial search and the Dirac equation c2004/10/190 v703 a 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. 1 aChilds, Andrew, M.1 aGoldstone, Jeffrey uhttp://arxiv.org/abs/quant-ph/0405120v101263nas a2200133 4500008004100000245003500041210003500076260001400111490000700125520090700132100002301039700002301062856004401085 2004 eng d00aSpatial search by quantum walk0 aSpatial search by quantum walk c2004/8/230 v703 a 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. 1 aChilds, Andrew, M.1 aGoldstone, Jeffrey uhttp://arxiv.org/abs/quant-ph/0306054v200715nas a2200145 4500008004100000245006300041210006300104260001500167490000700182520026200189100002300451700002600474700002500500856004400525 2003 eng d00aLower bounds on the complexity of simulating quantum gates0 aLower bounds on the complexity of simulating quantum gates c2003/11/180 v683 a 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. 1 aChilds, Andrew, M.1 aHaselgrove, Henry, L.1 aNielsen, Michael, A. uhttp://arxiv.org/abs/quant-ph/0307190v101268nas a2200121 4500008004100000245004200041210004200083260001500125520091400140100002301054700002501077856004401102 2003 eng d00aQuantum algorithms for subset finding0 aQuantum algorithms for subset finding c2003/11/063 a 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. 1 aChilds, Andrew, M.1 aEisenberg, Jason, M. uhttp://arxiv.org/abs/quant-ph/0311038v200849nas a2200145 4500008004100000245009300041210006900134260001500203520037100218100001900589700001800608700001900626700001400645856004400659 2002 eng d00aAsymptotic entanglement capacity of the Ising and anisotropic Heisenberg interactions 0 aAsymptotic entanglement capacity of the Ising and anisotropic He c2002/07/103 a 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. 1 aChilds, A., M.1 aLeung, D., W.1 aVerstraete, F.1 aVidal, G. uhttp://arxiv.org/abs/quant-ph/0207052v201113nas a2200169 4500008004100000245005200041210005200093260001500145520061800160100002300778700001900801700001900820700001800839700001700857700002500874856004400899 2002 eng d00aExponential algorithmic speedup by quantum walk0 aExponential algorithmic speedup by quantum walk c2002/09/243 a 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. 1 aChilds, Andrew, M.1 aCleve, Richard1 aDeotto, Enrico1 aFarhi, Edward1 aGutmann, Sam1 aSpielman, Daniel, A. uhttp://arxiv.org/abs/quant-ph/0209131v201071nas a2200181 4500008004100000245003400041210003400075260001400109490000700123520059100130100002300721700001900744700001800763700002300781700001700804700002400821856004400845 2002 eng d00aQuantum search by measurement0 aQuantum search by measurement c2002/9/230 v663 a 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. 1 aChilds, Andrew, M.1 aDeotto, Enrico1 aFarhi, Edward1 aGoldstone, Jeffrey1 aGutmann, Sam1 aLandahl, Andrew, J. uhttp://arxiv.org/abs/quant-ph/0204013v101113nas a2200169 4500008004100000245006000041210006000101260001400161490000700175520059300182100002500775700002500800700002300825700002300848700002800871856004400899 2002 eng d00aUniversal simulation of Hamiltonian dynamics for qudits0 aUniversal simulation of Hamiltonian dynamics for qudits c2002/8/300 v663 a 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. 1 aNielsen, Michael, A.1 aBremner, Michael, J.1 aDodd, Jennifer, L.1 aChilds, Andrew, M.1 aDawson, Christopher, M. uhttp://arxiv.org/abs/quant-ph/0109064v201212nas a2200145 4500008004100000245007400041210006900115260001400184490000700198520074500205100002300950700002400973700002500997856004401022 2001 eng d00aExact sampling from non-attractive distributions using summary states0 aExact sampling from nonattractive distributions using summary st c2001/2/220 v633 a 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. 1 aChilds, Andrew, M.1 aPatterson, Ryan, B.1 aMacKay, David, J. C. uhttp://arxiv.org/abs/cond-mat/0005132v100814nas a2200157 4500008004100000245007600041210006900117260001500186300001200201490000600213520033500219100002300554700001800577700001700595856004400612 2001 eng d00aAn example of the difference between quantum and classical random walks0 aexample of the difference between quantum and classical random w c2002/04/01 a35 - 430 v13 a 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. 1 aChilds, Andrew, M.1 aFarhi, Edward1 aGutmann, Sam uhttp://arxiv.org/abs/quant-ph/0103020v101006nas a2200145 4500008004100000245005300041210005300094260001400147490000700161520058100168100002300749700002200772700002200794856004400816 2001 eng d00aRealization of quantum process tomography in NMR0 aRealization of quantum process tomography in NMR c2001/6/130 v643 a 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. 1 aChilds, Andrew, M.1 aChuang, Isaac, L.1 aLeung, Debbie, W. uhttp://arxiv.org/abs/quant-ph/0012032v100767nas a2200145 4500008004100000245004800041210004800089260001500137490000700152520035800159100002300517700001800540700001900558856004400577 2001 eng d00aRobustness of adiabatic quantum computation0 aRobustness of adiabatic quantum computation c2001/12/140 v653 a 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. 1 aChilds, Andrew, M.1 aFarhi, Edward1 aPreskill, John uhttp://arxiv.org/abs/quant-ph/0108048v100953nas a2200109 4500008004100000245004000041210004000081260001500121520064000136100002300776856004400799 2001 eng d00aSecure assisted quantum computation0 aSecure assisted quantum computation c2001/11/073 a 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. 1 aChilds, Andrew, M. uhttp://arxiv.org/abs/quant-ph/0111046v201258nas a2200181 4500008004100000245005500041210005500096260001400151490000700165520074300172100001600915700002300931700002200954700001700976700002200993700001701015856004401032 2001 eng d00aUniversal simulation of Markovian quantum dynamics0 aUniversal simulation of Markovian quantum dynamics c2001/11/90 v643 a 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. 1 aBacon, Dave1 aChilds, Andrew, M.1 aChuang, Isaac, L.1 aKempe, Julia1 aLeung, Debbie, W.1 aZhou, Xinlan uhttp://arxiv.org/abs/quant-ph/0008070v201120nas a2200145 4500008004100000245005100041210005100092260001500143520069100158100002300849700001800872700002300890700001700913856004400930 2000 eng d00aFinding cliques by quantum adiabatic evolution0 aFinding cliques by quantum adiabatic evolution c2000/12/193 a 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. 1 aChilds, Andrew, M.1 aFarhi, Edward1 aGoldstone, Jeffrey1 aGutmann, Sam uhttp://arxiv.org/abs/quant-ph/0012104v101129nas a2200157 4500008004100000245005000041210005000091260001500141300001400156490000700170520069000177100002300867700001900890700001800909856004400927 2000 eng d00aQuantum information and precision measurement0 aQuantum information and precision measurement c1999/04/07 a155 - 1760 v473 a 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. 1 aChilds, Andrew, M.1 aPreskill, John1 aRenes, Joseph uhttp://arxiv.org/abs/quant-ph/9904021v200976nas a2200133 4500008004100000245006200041210006100103260001500164490000700179520056700186100002300753700002200776856004400798 2000 eng d00aUniversal quantum computation with two-level trapped ions0 aUniversal quantum computation with twolevel trapped ions c2000/12/110 v633 a 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. 1 aChilds, Andrew, M.1 aChuang, Isaac, L. uhttp://arxiv.org/abs/quant-ph/0008065v1