Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

On Quantum Search, Experts and Geometry

Milosh Drezgich

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

The problem of unstructured search plays the central role in our current understanding of the computational power of quantum computers. Improvement in the efficiency of solving unstructured search problem has an immediate consequence in the improvement in solving NP-complete problems. We introduce the new framework of natural continuous time quantum search algorithms, that in contrast to the adiabatic quantum algorithms, require neither the ground state initialization nor the adiabatic change of the Hamiltonian parameters. We moreover provide the concrete examples of transliteration from the unique marked element unstructured search problem into the particular class of quantum Hamiltonians, that facilitate the search in quantum continuous constant time. Since it is not clear how to implement that class of Hamiltonians one can either consider this result as a step toward proving that NP is a subset of BQP or as an indication that, that class of Hamiltonians is NP-hard to implement.Multiplicative weights update rule has been used in a few different fields as the underlying algorithmic structure. In its two different forms, vector and matrix, multiplicative update method provided a surprising simplicity and promised a small performance regret. We derive a slightly more general bound for the cumulative matrix multiplicative weights algorithm and introduce the iterative (streaming) matrix multiplicative weights algorithm with the same computational complexity and regret bound. In particular we also define the iterative Hadamard updates, matrix multiplicative updates algorithm, with the improved computational complexity for nonnegative games, from O(n³) to O(n²), and the same regret bound.Furthermore, we address the following question:"What is the minimal size quantum circuit required to exactly implement a specified nqubit unitary operation U, without the use of ancilla qubits?" Nielsen proved that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity I and U, where the length is defined by a suitable Finsler metric on SU(2ⁿ). We prove that the minimum circuit size that simulates U is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure F. As a corollary we prove the highest lower bound and the lowest upper bound for the standard simulation technique, that show that by standard simulation one can not expect a better then n² times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.Finally we investigate the n-dimensional hypercube quantum random walk (QRW) as a particularly appealing example of a quantum walk because it has a natural implementation on a register on n qubits. However, any real implementation will encounter decoherence effects due to interactions with uncontrollable degrees of freedom. We present a complete characterization of the mixing properties of the hypercube QRW under a physically relevant Markovian decoherence model. In the local decoherence model considered the non-unitary dynamics are modeled as a sum of projections on individual qubits to an arbitrary direction on the Bloch sphere. We prove that there is always a classical asymptotic mixing in this model and specify the conditions under which instantaneous mixing always exists. We show that the latter mixing property, as well as the classical mixing time, depend heavily on the exact environmental interaction and its strength. Therefore, algorithmic applications of the QRW on the hypercube, if they intend to employ mixing properties, need to consider both the walk dynamics and the precise decoherence model.

Related papers

Unstructured Adiabatic Quantum Optimization: Optimality with Limitations

Arthur Braida, Shantanav Chakraborty, Alapan Chaudhuri +4 more

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

arXiv:2411.05736•Quantum•Jul 11, 2025•2 citations

On New Quantum Search Algorithms and Complexity of NP-Complete Problems

Dhananjay P. Mehendale

We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!

•Jul 1, 2016•0 citations

Quantum information processing in continuous time

Andrew M. Childs, Edward Farhi

Quantum mechanical computers can solve certain problems asymptotically faster than any classical computing device. Several fast quantum algorithms are known, but the nature of quantum speedup is not well understood, and inventing new quantum algorithms seems to be difficult. In this thesis, we explore two approaches to designing quantum algorithms based on continuous-time Hamiltonian dynamics. In quantum computation by adiabatic evolution, the computer is prepared in the known ground state of a simple Hamiltonian, which is slowly modified so that its ground state encodes the solution to a problem. We argue that this approach should be inherently robust against low-temperature thermal noise and certain control errors, and we support this claim using simulations. We then show that any adiabatic algorithm can be implemented in a different way, using only a sequence of measurements of the Hamiltonian. We illustrate how this approach can achieve quadratic speedup for the unstructured search problem. We also demonstrate two examples of quantum speedup by quantum walk, a quantum mechanical analog of random walk. First, we consider the problem of searching a region

•Jan 1, 2004•79 citations

Continuous-time Quantum Algorithms: Searching and Adiabatic Computation

Lawrence M. Ioannou

One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.

•Jan 1, 2002•4 citations

Introducing structure to expedite quantum searching

Marcin Briański, Jan Gwinner, Vladyslav Hlembotskyi +3 more

We present a quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on noisy intermediate-scale quantum devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are, in fact, not unstructured, we also describe the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use an asymptotically smaller number of elementary gates than Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example, Unique $k$-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.

arXiv:2006.05828•Physical Review A•Jun 28, 2021•13 citations

On the Quantum Circuit Complexity Equivalence

Milosh Drezgich, Shankar Sastry

Nielsen \cite{Nielsen05} recently asked the following question: "What is the minimal size quantum circuit required to exactly implement a specified $% \mathit{n}$-qubit unitary operation $U$, without the use of ancilla qubits?" Nielsen was able to prove that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity $I$ and $U$, where the length is defined by a suitable Finsler metric on $SU(2^{n})$. We prove that the minimum circuit size that simulates $U$ is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure $F$. As a corollary we prove the highest lower bound of $O(\frac{% n^{4}}{p}d_{F_{p}}^{2}(I,U)L_{F_{p}}(I,\tilde{U})) $and the lowest upper bound of $Ω(n^{4}d_{F_{p}}^{3}(I,U))$, for the standard simulation technique. Therefore, our results show that by standard simulation one can not expect a better then $n^{2}$ times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty \cite{Nielsen06}. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.

arXiv:quant-ph/0703082•Mar 9, 2007•1 citation
The problem of unstructured search plays the central role in our current understanding of the computational power of quantum computers. Improvement in the efficiency of solving unstructured search problem has an immediate consequence in the improvement in solving NP-complete problems. We introduce the new framework of natural continuous time quantum search algorithms, that in contrast to the adiabatic quantum algorithms, require neither the ground state initialization nor the adiabatic change of the Hamiltonian parameters. We moreover provide the concrete examples of transliteration from the unique marked element unstructured search problem into the particular class of quantum Hamiltonians, that facilitate the search in quantum continuous constant time. Since it is not clear how to implement that class of Hamiltonians one can either consider this result as a step toward proving that NP is a subset of BQP or as an indication that, that class of Hamiltonians is NP-hard to implement.Multiplicative weights update rule has been used in a few different fields as the underlying algorithmic structure. In its two different forms, vector and matrix, multiplicative update method provided a surprising simplicity and promised a small performance regret. We derive a slightly more general bound for the cumulative matrix multiplicative weights algorithm and introduce the iterative (streaming) matrix multiplicative weights algorithm with the same computational complexity and regret bound. In particular we also define the iterative Hadamard updates, matrix multiplicative updates algorithm, with the improved computational complexity for nonnegative games, from O(n³) to O(n²), and the same regret bound.Furthermore, we address the following question:"What is the minimal size quantum circuit required to exactly implement a specified nqubit unitary operation U, without the use of ancilla qubits?" Nielsen proved that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity I and U, where the length is defined by a suitable Finsler metric on SU(2ⁿ). We prove that the minimum circuit size that simulates U is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure F. As a corollary we prove the highest lower bound and the lowest upper bound for the standard simulation technique, that show that by standard simulation one can not expect a better then n² times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.Finally we investigate the n-dimensional hypercube quantum random walk (QRW) as a particularly appealing example of a quantum walk because it has a natural implementation on a register on n qubits. However, any real implementation will encounter decoherence effects due to interactions with uncontrollable degrees of freedom. We present a complete characterization of the mixing properties of the hypercube QRW under a physically relevant Markovian decoherence model. In the local decoherence model considered the non-unitary dynamics are modeled as a sum of projections on individual qubits to an arbitrary direction on the Bloch sphere. We prove that there is always a classical asymptotic mixing in this model and specify the conditions under which instantaneous mixing always exists. We show that the latter mixing property, as well as the classical mixing time, depend heavily on the exact environmental interaction and its strength. Therefore, algorithmic applications of the QRW on the hypercube, if they intend to employ mixing properties, need to consider both the walk dynamics and the precise decoherence model.
In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.
We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!
Quantum mechanical computers can solve certain problems asymptotically faster than any classical computing device. Several fast quantum algorithms are known, but the nature of quantum speedup is not well understood, and inventing new quantum algorithms seems to be difficult. In this thesis, we explore two approaches to designing quantum algorithms based on continuous-time Hamiltonian dynamics. In quantum computation by adiabatic evolution, the computer is prepared in the known ground state of a simple Hamiltonian, which is slowly modified so that its ground state encodes the solution to a problem. We argue that this approach should be inherently robust against low-temperature thermal noise and certain control errors, and we support this claim using simulations. We then show that any adiabatic algorithm can be implemented in a different way, using only a sequence of measurements of the Hamiltonian. We illustrate how this approach can achieve quadratic speedup for the unstructured search problem. We also demonstrate two examples of quantum speedup by quantum walk, a quantum mechanical analog of random walk. First, we consider the problem of searching a region
One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.
We present a quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on noisy intermediate-scale quantum devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are, in fact, not unstructured, we also describe the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use an asymptotically smaller number of elementary gates than Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example, Unique kkk-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.
Nielsen \cite{Nielsen05} recently asked the following question: "What is the minimal size quantum circuit required to exactly implement a specified % \mathit{n}-qubit unitary operation UUU, without the use of ancilla qubits?" Nielsen was able to prove that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity III and UUU, where the length is defined by a suitable Finsler metric on SU(2n)SU(2^{n})SU(2n). We prove that the minimum circuit size that simulates UUU is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure FFF. As a corollary we prove the highest lower bound of $O(\frac{% n^{4}}{p}d_{F_{p}}^{2}(I,U)L_{F_{p}}(I,\tilde{U})) $and the lowest upper bound of Ω(n4dFp3(I,U))Ω(n^{4}d_{F_{p}}^{3}(I,U))Ω(n4dFp​3​(I,U)), for the standard simulation technique. Therefore, our results show that by standard simulation one can not expect a better then n2n^{2}n2 times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty \cite{Nielsen06}. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.