arXiv:quant-ph/9612026

An Analog Analogue of a Digital Quantum Computation

Edward Farhi, Sam Gutmann

Published Dec 6, 1996• 15 citations

Abstract

We solve a problem, which while not fitting into the usual paradigm, can be viewed as a quantum computation. Suppose we are given a quantum system described by an N dimensional Hilbert space with a Hamiltonian of the form $E |w >< w|$ where $| w>$ is an unknown (normalized) state. We show how to discover $| w >$ by adding a Hamiltonian (independent of $| w >$) and evolving for a time proportional to $N^{1/2}/E$. We show that this time is optimally short. This process is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer which locates a marked item from an unsorted list of N items in a number of steps proportional to $N^{1/2}$.

DOI: 10.48550/arxiv.quant-ph/9612026

Related papers

Analog analogue of a digital quantum computation

Edward Farhi, Sam Gutmann

Physical Review AApr 1, 1998382 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

InTech eBooksApr 26, 20110 citations

Quantum search with variable times

Andris Ambainis

arXiv:quant-ph/0609168Sep 21, 20061 citation

Hamiltonian and Measuring Time for Analog Quantum Search

Jin-Yuan Hsieh, Che-Ming Li, Der-San Chuu

We derive in this study a Hamiltonian to solve with certainty the analog quantum search problem analogue to the Grover algorithm. The general form of the initial state is considered. Since the evaluation of the measuring time for finding the marked state by probability of unity is crucially important in the problem, especially when the Bohr frequency is high, we then give the exact formula as a function of all given parameters for the measuring time.

arXiv:quant-ph/0209092Journal of the Physical Society of JapanNov 15, 20051 citation

Quantum Search with Variable Times

Andris Ambainis

Theory of Computing SystemsJun 2, 200940 citations

Hamiltonian simulation with explicit formulas for Digital-Analog Quantum Computing

Mikel Garcia-de-Andoin, Thorge Müller, Gonzalo Camacho

quant-pharXiv:2511.11404Physical Review ANov 17, 20250 citations

arXiv:quant-ph/9612026

An Analog Analogue of a Digital Quantum Computation

Edward Farhi, Sam Gutmann

Published Dec 6, 1996• 15 citations

arXiv HTML PDF

Abstract

E |w >< w|

where

| w>

is an unknown (normalized) state. We show how to discover

| w >

by adding a Hamiltonian (independent of

| w >

) and evolving for a time proportional to

N^{1/2}/E

. We show that this time is optimally short. This process is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer which locates a marked item from an unsorted list of N items in a number of steps proportional to

N^{1/2}

DOI: 10.48550/arxiv.quant-ph/9612026

Related papers

Analog analogue of a digital quantum computation

Edward Farhi, Sam Gutmann

We solve a problem, which while not fitting into the usual paradigm, can be viewed as a quantum computation. Suppose we are given a quantum system with a Hamiltonian of the form $E|w〉〈w|$ where $|w〉$ is an unknown (normalized) state. The problem is to produce $|w〉$ by adding a Hamiltonian (independent of $|w〉)$ and evolving the system. If $|w〉$ is chosen uniformly at random we can (with high probability) produce $|w〉$ in a time proportional to ${N}^{1/2}/E$ . If $|w〉$ is instead chosen from a fixed, known orthonormal basis we can also produce $|w〉$ in a time proportional to ${N}^{1/2}/E$ and we show that this time is optimally short. This restricted problem is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer that locates a marked item from an unsorted list of $N$ items in a number of steps proportional to ${N}^{1/2}$ .We solve a problem, which while not fitting into the usual paradigm, can be viewed as a quantum computation. Suppose we are given a quantum system with a Hamiltonian of the form $E|w〉〈w|$ where $|w〉$ is an unknown (normalized) state. The problem is to produce $|w〉$ by adding a Hamiltonian (independent of $|w〉)$ and evolving the system. If $|w〉$ is chosen uniformly at random we can (with high probability) produce $|w〉$ in a time proportional to ${N}^{1/2}/E$. If $|w〉$ is instead chosen from a fixed, known orthonormal basis we can also produce $|w〉$ in a time proportional to ${N}^{1/2}/E$ and we show that this time is optimally short. This restricted problem is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer that locates a marked item from an unsorted list of $N$ items in a number of steps proportional to ${N}^{1/2}$.

Physical Review AApr 1, 1998382 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooksApr 26, 20110 citations

Quantum search with variable times

Andris Ambainis

Since Grover's seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items and we would like to find a marked item. We consider a new variant of this problem in which evaluating the i-th item may take a different number of time steps for different i. Let t_i be the number of time steps required to evaluate the i-th item. If the numbers t_i are known in advance, we give an algorithm that solves the problem in O(\sqrt{t_1^2+t_2^2+...+t_n^2}) steps. This is optimal, as we also show a matching lower bound. The case, when t_i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.Since Grover's seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items and we would like to find a marked item. We consider a new variant of this problem in which evaluating the i-th item may take a different number of time steps for different i. Let t_i be the number of time steps required to evaluate the i-th item. If the numbers t_i are known in advance, we give an algorithm that solves the problem in O(\sqrt{t_1^2+t_2^2+...+t_n^2}) steps. This is optimal, as we also show a matching lower bound. The case, when t_i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.

arXiv:quant-ph/0609168Sep 21, 20061 citation

Hamiltonian and Measuring Time for Analog Quantum Search

Jin-Yuan Hsieh, Che-Ming Li, Der-San Chuu

arXiv:quant-ph/0209092Journal of the Physical Society of JapanNov 15, 20051 citation

Quantum Search with Variable Times

Andris Ambainis

Since Grover’s seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items x 1,…,x n and we would like to find i:x i =1. We consider a new variant of this problem in which evaluating x i for different i may take a different number of time steps. Let t i be the number of time steps required to evaluate x i . If the numbers t i are known in advance, we give an algorithm that solves the problem in $O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})$ steps. This is optimal, as we also show a matching lower bound. The case, when t i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.Since Grover’s seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items x 1,…,x n and we would like to find i:x i =1. We consider a new variant of this problem in which evaluating x i for different i may take a different number of time steps. Let t i be the number of time steps required to evaluate x i . If the numbers t i are known in advance, we give an algorithm that solves the problem in $O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})$ steps. This is optimal, as we also show a matching lower bound. The case, when t i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.

Theory of Computing SystemsJun 2, 200940 citations

Hamiltonian simulation with explicit formulas for Digital-Analog Quantum Computing

Mikel Garcia-de-Andoin, Thorge Müller, Gonzalo Camacho

Digital-analog is a quantum computational paradigm that employs the natural interaction Hamiltonian of a system as the entangling resource, combined with single qubit gates, to implement universal quantum operations. As in the case of its digital gate-based counterpart, designing digital-analog circuits that employ optimal quantum resources often requires an exceedingly large classical computational time. In this work we find a suboptimal solution to this exponentially large problem, showing that it can be solved within polynomial computational time. In particular, we provide an exact solution for the problem of expressing arbitrary two-body Hamiltonians as the sum of local unitary transformations of an arbitrary Ising Hamiltonian, with the total number of required terms being at most quadratic in system size. This allows us to design a digital-analog simulation protocol that avoids employing numerical optimization over a large parameter space at the preprocessing stage, minimizing computational resources and allowing for further scaling.Digital-analog is a quantum computational paradigm that employs the natural interaction Hamiltonian of a system as the entangling resource, combined with single qubit gates, to implement universal quantum operations. As in the case of its digital gate-based counterpart, designing digital-analog circuits that employ optimal quantum resources often requires an exceedingly large classical computational time. In this work we find a suboptimal solution to this exponentially large problem, showing that it can be solved within polynomial computational time. In particular, we provide an exact solution for the problem of expressing arbitrary two-body Hamiltonians as the sum of local unitary transformations of an arbitrary Ising Hamiltonian, with the total number of required terms being at most quadratic in system size. This allows us to design a digital-analog simulation protocol that avoids employing numerical optimization over a large parameter space at the preprocessing stage, minimizing computational resources and allowing for further scaling.

quant-pharXiv:2511.11404Physical Review ANov 17, 20250 citations

E |w >< w|

where

| w>

is an unknown (normalized) state. We show how to discover

| w >

by adding a Hamiltonian (independent of

| w >

) and evolving for a time proportional to

N^{1/2}/E

N^{1/2}

We solve a problem, which while not fitting into the usual paradigm, can be viewed as a quantum computation. Suppose we are given a quantum system with a Hamiltonian of the form

E|w〉〈w|

where

|w〉

is an unknown (normalized) state. The problem is to produce

|w〉

by adding a Hamiltonian (independent of

|w〉)

and evolving the system. If

|w〉

is chosen uniformly at random we can (with high probability) produce

|w〉

in a time proportional to

{N}^{1/2}/E

. If

|w〉

is instead chosen from a fixed, known orthonormal basis we can also produce

|w〉

in a time proportional to

{N}^{1/2}/E

and we show that this time is optimally short. This restricted problem is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer that locates a marked item from an unsorted list of

N

items in a number of steps proportional to

{N}^{1/2}

O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})

steps. This is optimal, as we also show a matching lower bound. The case, when t i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.