![Quantum Algorithms and Lower Bounds in Continuous Time D. L. Yonge-Mallo (joint work with Richard Cleve) Institute for Quantum Computing, University of Waterloo Abstract Continuous-Time Quantum Algorithms Continuous-Time Adversary Lower Bounds Many models of quantum computation, such as the Turing machine model or the circuit model, The first continuous-time quantum algorithm was discovered at around the same time as (and inde- Quantum lower bounds are inherent limitations to the power of quantum computation. For any given treat time as a discrete quantity and describe algorithms as discrete sequences of steps. However, pendently of) its discrete counterpart, the famous Grover’s algorithm for searching an unstructured problem, knowing a lower bound allows us to gauge the optimality of any algorithm, and provides a this is not the only way to view quantum computational processes, as algorithms based on such database (see bottom). The line of research initiated by this discovery eventually culminated in a guide for the development of new algorithms. But more than that, because quantum computation is ideas as continuous-time quantum walks show. By studying the properties of quantum computation continuous-time quantum walk algorithm for evaluating A ND -O R trees, based on scattering theory a model of computation based on the most accurate descriptions of physics we know, quantum lower in a continuous-time framework, we hope to discover new algorithms, develop better intuitions into [FGG07]. That algorithm was subsequently discretized [CCJY07] and inspired a number of other bounds tell us about the computational power of the laws of Nature itself. existing algorithms, and gain further insights into the power and limitations of quantum computation. continuous-time algorithms [RS07,Chi08]. Finally, continuous-time quantum walk was recently The adversary method is a family of related quantum lower bound techniques, all of which are es- shown to be universal for quantum computation [Chi08]. ˇ sentially equivalent [SS06]. The basic idea behind the adversary method is this: if an algorithm computes a function, then it must be able to distinguish between inputs that map to different outputs. Discrete and Continuous Oracles Suppose that we wish to compute some function f : {0, 1}N → {0, 1} using a quantum computer, Continuing Research into Continuous Time A B |ψx(0) = |ψy (0) on some input string s = s1s2 · · · sN . We are allowed to access s only through a “black box” oracle, Despite a considerable amount of research, much is currently unknown about the power of the which we query with the index j in order to learn the bit sj . The query complexity of a particular continuous-time model. Clearly, it is at least as powerful as the discrete-time model, but are there w(x, y) y |ψx(T ) algorithm computing f is the number of queries it makes, and the query complexity of the function problems which can be solved asymptotically faster with calls to Hamiltonian oracles than to f is the minimum of this over all algorithms which compute f . discrete ones? Conversely, can every continuous-time quantum algorithm be simulated efficiently in x t=0 discrete time? The state of a quantum algorithm computing f at time t, given input s, can be written as: t=T There are some results which suggest that the two models are equivalent in terms of their asymptotic |ψs(t) = {αj (t) · |j ⊗ |b ⊗ |φj (t) } (1) cost. Along with our collaborators, we have shown that Hamiltonian oracles can be simulated |ψy (T ) j ∀a ∈ A{f (a) = 0} ∀b ∈ B{f (b) = 1} efficiently using discrete queries (see bottom left). Moreover, we have also shown that lower bounds index register and oracle qubit other registers obtained by the adversary method, one of the two main methods for discrete query quantum lower Figure 2: (left) Let A and B be the sets of inputs on which f evaluates to 0 and 1, respectively. In the discrete-time model, a call to the oracle flips the oracle qubit if and only if sj = 1: bounds, also apply in the continuous-time model (see top right). Thus, the two models are equivalent The difficulty of computing f can be measured by the difficulty of distinguishing between strings in power for the class of problems for which the adversary method gives the optimal lower bound. in A and strings in B. We can capture the difficulty of distinguishing between each pair of inputs Os|j ⊗ |b = |j ⊗ |b ⊕ sj However, it is currently unknown how to exactly characterize this class. Nevertheless, even if there (x, y) ∈ A × B by assigning a weight w(x, y) to it. (right) An algorithm can distinguish between is a gap between the two models, it is likely to be small. inputs x and y only if the quantum states corresponding to those inputs are (nearly) orthogonal after A quantum algorithm making T queries is a sequence of operations alternating between and unitary the algorithm has run for some time T . transformations, which do not depend on s, and calls to the oracle. If, when the final state |ψs(T ) of On the other hand, the adversary method does not give the optimal lower bound for many problems. the algorithm is measured, the output is correct with probability at least 2/3, the algorithm is said to Furthemore, nothing is known about how lower bounds obtained using the other major method, the Since a certain amount of information about the inputs is required to distinguish them, a lower bound compute f with bounded error. polynomial method, relate to continuous-time algorithms. What is the connection between lower for the query complexity of a function can be obtained by upper bounding the amount of information bounds and algorithms in the continuous-time model, and can lower bounds serve as a guide to revealed in each query. For an algorithm to be able to distinguish between x and y, ψx(t)|ψy (t) Z The discrete oracle applies a rotation by (sj · π) around the X |ψs(t) = |0 discovering algorithms and vice versa? What are the properties in this model of algorithms based must be small. We use this fact to define a progress measure: axis on the Bloch sphere to the qubit register. The model can be generalized by allowing a fraction 0 < τ < 1 of an entire on the quantum Fourier transform? How do the lower bound constants in the two models compare? Which problems are intuitively more easy to solve in this model than in the discrete-time one? Does w(t) = w(x, y) · ψx(t)|ψy (t) (4) rotation. The result in the limit τ → 0 is the continuous oracle, the relationship between the two models have consequences for complexity classes defined using (x,y)∈A×B τ ·π or Hamiltonian oracle. discrete queries? There are just some of the questions which need to be answered. There is still much In order for an algorithm to compute f with bounded error, w(t) must decrease from its initial value Figure 1: Suppose that the state of a quantum algorithm is research to be done on the properties of quantum algorithms and the power of quantum computation Y of |A| · |B| to (sufficiently close to) 0 at time T . Equations (2) and (4) together give an upper bound |ψs(t) = |j ⊗ |0 , with sj = 1. The Bloch sphere on the in the continuous-time model. to the rate of change of w(t): |ψs(t + τ ) left shows the result of an oracle call on the oracle qubit. One X application of the discrete oracle rotates it all the way to |1 ; d O O |ψs(t + 1) = |1 however, applying the Hamiltonian oracle for a time τ results Example: Unstructured database search dt w(t) ≤ (x,y)∈A×B w(x, y) · ψy (t)|(Hx − Hy )|ψx(t) (5) in the intermediate state |ψs(t + τ ) , as shown. Given a list of N items, one of which is marked, the unstructured database search problem is to The continuous-time model, introduced in [FG98] and further developed in [Moch06] and [FGG07], return the index of the marked item. The continuous-time algorithm of [FG98] solves this problem Integrating this from 0 to T results in a lower bound on T . √ generalizes the discrete-time model by allowing calls to the oracle and the part of the algorithm by making use of the Hamiltonian oracle for a time proportional to N , which is asymptotically the In general, it is not clear how to choose the weights w(x, y) or how to perform the integration – which does not depend on the input to happen concurrently. In this model, the algorithm state evolves same as the query complexity of Grover’s algorithm. A proof of the matching lower bound is given these depend on the problem. Thus far, the only problems for which we know how to apply the according to the Schr¨ dinger equation: o in that paper. Here, we illustrate the continuous-time adversary method by re-deriving this bound. continuous-time adversary method are the ones for which we already have a discrete query adversary d Consider the decision version of the problem: given an N -bit input s, determine whether it is the lower bound. (See the unstructured database search problem on the left for an example.) |ψs(t) = −i(Hs + H D (t))|ψs(t) O (2) dt all-zeros string, denoted by x. Let A be the set {x} and let B be the set of all other inputs. For each Hamiltonian oracle driving Hamiltonian y ∈ B, set w(x, y) to 1 if |y| = 1 and set it to 0 otherwise. By equation (4), the initial value of the References progress measure is w(0) = N , and its final value must be w(T ) = ε, where ε is close to 0. Since [Amb06] A. Ambainis, “Polynomial degree vs. query complexity”. J. Comp. & Sys. Sciences (JCSS), 72:220–238, 2006. O The Hamiltonian oracle Hs is specified by a matrix with s1, s2, . . . , sN on the diagonal and zeros O Hx is the zero matrix, equation (5) gives: [Chi08] A. Childs, “Universal computation by quantum walk”. arXiv:0806.1972. elsewhere. The discrete-time model can be simulated easily by the continuous-time model. In the [CCJY07] Childs, Cleve, Jordan, and Y., “Discrete-query quantum algorithm for NAND trees”. arXiv:quant-ph/0702160. other direction, the continuous-time model can be discretized under certain conditions, for example d O O √ [FG98] E. Farhi and S. Gutmann, “Analog analogue of a digital quantum computation”. Phys Rev A, 57(4):2403–2406, 1998. w(t) ≤ ψy (t)|Hy |ψx(t) ≤ Hy |ψx(t) ≤ N (3) [FGG07] Farhi, Goldstone, and Gutmann, “A Quantum Algorithm for the Hamiltonian NAND Tree”. arXiv:quant-ph/0702144. using the Suzuki-Trotter expansion. Recent work in collaboration with D. Gottesman, M. Mosca, and dt [Moch06] C. Mochon, “Hamiltonian oracles”. Phys Rev A, 75:042313, 2007. |y|=1 |y|=1 R. Somma show that any continuous-time quantum algorithm making use of a Hamiltonian oracle [RS07] ˇ B. Reichardt and R. Spalek, “Span-program-based quantum algorithm for evaluating formulas”. arXiv:0710.2630. for time O(T ) can be simulated using O(T log T ) discrete queries and known unitary operations. √ ˇ [SS06] ˇ R. Spalek and M. Szegedy. “All quantum adversary methods are equivalent”. Theory of Computing, 2(1):1–18, 2006. Thus, any continuous-time quantum algorithm must call the Hamiltonian oracle for time O( N ).](https://image.slidesharecdn.com/buckhead-final-090819153944-phpapp01/75/Quantum-Algorithms-and-Lower-Bounds-in-Continuous-Time-1-2048.jpg)
Uploaded byDavid Yonge-Mallo
Quantum Algorithms and Lower Bounds in Continuous Time
This document discusses continuous-time quantum algorithms and their relationship with discrete-time models, highlighting the significance of lower bounds in quantum computation. It introduces the continuous-time adversary method and explores the query complexity of quantum functions, suggesting that continuous-time models may be as powerful as their discrete counterparts. The research indicates the need for further exploration into the properties and limitations of continuous-time quantum algorithms.
Quantum Algorithms and Lower Bounds in Continuous Time
- 1. Quantum Algorithms andLower Bounds in Continuous Time D. L. Yonge-Mallo (joint work with Richard Cleve) Institute for Quantum Computing, University of Waterloo Abstract Continuous-Time Quantum Algorithms Continuous-Time Adversary Lower Bounds Many models of quantum computation, such as the Turing machine model or the circuit model, The first continuous-time quantum algorithm was discovered at around the same time as (and inde- Quantum lower bounds are inherent limitations to the power of quantum computation. For any given treat time as a discrete quantity and describe algorithms as discrete sequences of steps. However, pendently of) its discrete counterpart, the famous Grover’s algorithm for searching an unstructured problem, knowing a lower bound allows us to gauge the optimality of any algorithm, and provides a this is not the only way to view quantum computational processes, as algorithms based on such database (see bottom). The line of research initiated by this discovery eventually culminated in a guide for the development of new algorithms. But more than that, because quantum computation is ideas as continuous-time quantum walks show. By studying the properties of quantum computation continuous-time quantum walk algorithm for evaluating A ND -O R trees, based on scattering theory a model of computation based on the most accurate descriptions of physics we know, quantum lower in a continuous-time framework, we hope to discover new algorithms, develop better intuitions into [FGG07]. That algorithm was subsequently discretized [CCJY07] and inspired a number of other bounds tell us about the computational power of the laws of Nature itself. existing algorithms, and gain further insights into the power and limitations of quantum computation. continuous-time algorithms [RS07,Chi08]. Finally, continuous-time quantum walk was recently The adversary method is a family of related quantum lower bound techniques, all of which are es- shown to be universal for quantum computation [Chi08]. ˇ sentially equivalent [SS06]. The basic idea behind the adversary method is this: if an algorithm computes a function, then it must be able to distinguish between inputs that map to different outputs. Discrete and Continuous Oracles Suppose that we wish to compute some function f : {0, 1}N → {0, 1} using a quantum computer, Continuing Research into Continuous Time A B |ψx(0) = |ψy (0) on some input string s = s1s2 · · · sN . We are allowed to access s only through a “black box” oracle, Despite a considerable amount of research, much is currently unknown about the power of the which we query with the index j in order to learn the bit sj . The query complexity of a particular continuous-time model. Clearly, it is at least as powerful as the discrete-time model, but are there w(x, y) y |ψx(T ) algorithm computing f is the number of queries it makes, and the query complexity of the function problems which can be solved asymptotically faster with calls to Hamiltonian oracles than to f is the minimum of this over all algorithms which compute f . discrete ones? Conversely, can every continuous-time quantum algorithm be simulated efficiently in x t=0 discrete time? The state of a quantum algorithm computing f at time t, given input s, can be written as: t=T There are some results which suggest that the two models are equivalent in terms of their asymptotic |ψs(t) = {αj (t) · |j ⊗ |b ⊗ |φj (t) } (1) cost. Along with our collaborators, we have shown that Hamiltonian oracles can be simulated |ψy (T ) j ∀a ∈ A{f (a) = 0} ∀b ∈ B{f (b) = 1} efficiently using discrete queries (see bottom left). Moreover, we have also shown that lower bounds index register and oracle qubit other registers obtained by the adversary method, one of the two main methods for discrete query quantum lower Figure 2: (left) Let A and B be the sets of inputs on which f evaluates to 0 and 1, respectively. In the discrete-time model, a call to the oracle flips the oracle qubit if and only if sj = 1: bounds, also apply in the continuous-time model (see top right). Thus, the two models are equivalent The difficulty of computing f can be measured by the difficulty of distinguishing between strings in power for the class of problems for which the adversary method gives the optimal lower bound. in A and strings in B. We can capture the difficulty of distinguishing between each pair of inputs Os|j ⊗ |b = |j ⊗ |b ⊕ sj However, it is currently unknown how to exactly characterize this class. Nevertheless, even if there (x, y) ∈ A × B by assigning a weight w(x, y) to it. (right) An algorithm can distinguish between is a gap between the two models, it is likely to be small. inputs x and y only if the quantum states corresponding to those inputs are (nearly) orthogonal after A quantum algorithm making T queries is a sequence of operations alternating between and unitary the algorithm has run for some time T . transformations, which do not depend on s, and calls to the oracle. If, when the final state |ψs(T ) of On the other hand, the adversary method does not give the optimal lower bound for many problems. the algorithm is measured, the output is correct with probability at least 2/3, the algorithm is said to Furthemore, nothing is known about how lower bounds obtained using the other major method, the Since a certain amount of information about the inputs is required to distinguish them, a lower bound compute f with bounded error. polynomial method, relate to continuous-time algorithms. What is the connection between lower for the query complexity of a function can be obtained by upper bounding the amount of information bounds and algorithms in the continuous-time model, and can lower bounds serve as a guide to revealed in each query. For an algorithm to be able to distinguish between x and y, ψx(t)|ψy (t) Z The discrete oracle applies a rotation by (sj · π) around the X |ψs(t) = |0 discovering algorithms and vice versa? What are the properties in this model of algorithms based must be small. We use this fact to define a progress measure: axis on the Bloch sphere to the qubit register. The model can be generalized by allowing a fraction 0 < τ < 1 of an entire on the quantum Fourier transform? How do the lower bound constants in the two models compare? Which problems are intuitively more easy to solve in this model than in the discrete-time one? Does w(t) = w(x, y) · ψx(t)|ψy (t) (4) rotation. The result in the limit τ → 0 is the continuous oracle, the relationship between the two models have consequences for complexity classes defined using (x,y)∈A×B τ ·π or Hamiltonian oracle. discrete queries? There are just some of the questions which need to be answered. There is still much In order for an algorithm to compute f with bounded error, w(t) must decrease from its initial value Figure 1: Suppose that the state of a quantum algorithm is research to be done on the properties of quantum algorithms and the power of quantum computation Y of |A| · |B| to (sufficiently close to) 0 at time T . Equations (2) and (4) together give an upper bound |ψs(t) = |j ⊗ |0 , with sj = 1. The Bloch sphere on the in the continuous-time model. to the rate of change of w(t): |ψs(t + τ ) left shows the result of an oracle call on the oracle qubit. One X application of the discrete oracle rotates it all the way to |1 ; d O O |ψs(t + 1) = |1 however, applying the Hamiltonian oracle for a time τ results Example: Unstructured database search dt w(t) ≤ (x,y)∈A×B w(x, y) · ψy (t)|(Hx − Hy )|ψx(t) (5) in the intermediate state |ψs(t + τ ) , as shown. Given a list of N items, one of which is marked, the unstructured database search problem is to The continuous-time model, introduced in [FG98] and further developed in [Moch06] and [FGG07], return the index of the marked item. The continuous-time algorithm of [FG98] solves this problem Integrating this from 0 to T results in a lower bound on T . √ generalizes the discrete-time model by allowing calls to the oracle and the part of the algorithm by making use of the Hamiltonian oracle for a time proportional to N , which is asymptotically the In general, it is not clear how to choose the weights w(x, y) or how to perform the integration – which does not depend on the input to happen concurrently. In this model, the algorithm state evolves same as the query complexity of Grover’s algorithm. A proof of the matching lower bound is given these depend on the problem. Thus far, the only problems for which we know how to apply the according to the Schr¨ dinger equation: o in that paper. Here, we illustrate the continuous-time adversary method by re-deriving this bound. continuous-time adversary method are the ones for which we already have a discrete query adversary d Consider the decision version of the problem: given an N -bit input s, determine whether it is the lower bound. (See the unstructured database search problem on the left for an example.) |ψs(t) = −i(Hs + H D (t))|ψs(t) O (2) dt all-zeros string, denoted by x. Let A be the set {x} and let B be the set of all other inputs. For each Hamiltonian oracle driving Hamiltonian y ∈ B, set w(x, y) to 1 if |y| = 1 and set it to 0 otherwise. By equation (4), the initial value of the References progress measure is w(0) = N , and its final value must be w(T ) = ε, where ε is close to 0. Since [Amb06] A. Ambainis, “Polynomial degree vs. query complexity”. J. Comp. & Sys. Sciences (JCSS), 72:220–238, 2006. O The Hamiltonian oracle Hs is specified by a matrix with s1, s2, . . . , sN on the diagonal and zeros O Hx is the zero matrix, equation (5) gives: [Chi08] A. Childs, “Universal computation by quantum walk”. arXiv:0806.1972. elsewhere. The discrete-time model can be simulated easily by the continuous-time model. In the [CCJY07] Childs, Cleve, Jordan, and Y., “Discrete-query quantum algorithm for NAND trees”. arXiv:quant-ph/0702160. other direction, the continuous-time model can be discretized under certain conditions, for example d O O √ [FG98] E. Farhi and S. Gutmann, “Analog analogue of a digital quantum computation”. Phys Rev A, 57(4):2403–2406, 1998. w(t) ≤ ψy (t)|Hy |ψx(t) ≤ Hy |ψx(t) ≤ N (3) [FGG07] Farhi, Goldstone, and Gutmann, “A Quantum Algorithm for the Hamiltonian NAND Tree”. arXiv:quant-ph/0702144. using the Suzuki-Trotter expansion. Recent work in collaboration with D. Gottesman, M. Mosca, and dt [Moch06] C. Mochon, “Hamiltonian oracles”. Phys Rev A, 75:042313, 2007. |y|=1 |y|=1 R. Somma show that any continuous-time quantum algorithm making use of a Hamiltonian oracle [RS07] ˇ B. Reichardt and R. Spalek, “Span-program-based quantum algorithm for evaluating formulas”. arXiv:0710.2630. for time O(T ) can be simulated using O(T log T ) discrete queries and known unitary operations. √ ˇ [SS06] ˇ R. Spalek and M. Szegedy. “All quantum adversary methods are equivalent”. Theory of Computing, 2(1):1–18, 2006. Thus, any continuous-time quantum algorithm must call the Hamiltonian oracle for time O( N ).