Grover's algorithm can solve NP-complete problems on quantum computers faster than all the known algorithms on classical computers. However, Grover's algorithm still needs exponential time. Due to the BBBV theorem, Grover's algorithm is optimal for searches in the domain of a function, when the function is used as a black box. We analyze the NP-complete set $\{ (\langle M \rangle, 1^n, 1^t ) \mid \text{ TM }M\text{ accepts an }x\in\{0,1\}^n\text{ within }t\text{ steps}\}.$ If $t$ is large enough, then M accepts each word in $L(M)$ with length $n$ within $t$ steps. So, one can use methods from computability theory to show that black box searching is the fastest way to find a solution. Therefore, Grover's algorithm is optimal for NP-complete problems.Grover's algorithm can solve NP-complete problems on quantum computers faster than all the known algorithms on classical computers. However, Grover's algorithm still needs exponential time. Due to the BBBV theorem, Grover's algorithm is optimal for searches in the domain of a function, when the function is used as a black box. We analyze the NP-complete set \[\{ (\langle M \rangle, 1^n, 1^t ) \mid \text{ TM }M\text{ accepts an }x\in\{0,1\}^n\text{ within }t\text{ steps}\}.\] If $t$ is large enough, then M accepts each word in $L(M)$ with length $n$ within $t$ steps. So, one can use methods from computability theory to show that black box searching is the fastest way to find a solution. Therefore, Grover's algorithm is optimal for NP-complete problems.

arXiv:2311.05624Jul 10, 20230 citations

Global Optimization With Quantum Walk Enhanced Grover Search

Yan Wang

One of the significant breakthroughs in quantum computation is Grover’s algorithm for unsorted database search. Recently, the applications of Grover’s algorithm to solve global optimization problems have been demonstrated, where unknown optimum solutions are found by iteratively improving the threshold value for the selective phase shift operator in Grover rotation. In this paper, a hybrid approach that combines continuous-time quantum walks with Grover search is proposed. By taking advantage of quantum tunneling effect, local barriers are overcome and better threshold values can be found at the early stage of search process. The new algorithm based on the formalism is demonstrated with benchmark examples of global optimization. The results between the new algorithm and the Grover search method are also compared.One of the significant breakthroughs in quantum computation is Grover’s algorithm for unsorted database search. Recently, the applications of Grover’s algorithm to solve global optimization problems have been demonstrated, where unknown optimum solutions are found by iteratively improving the threshold value for the selective phase shift operator in Grover rotation. In this paper, a hybrid approach that combines continuous-time quantum walks with Grover search is proposed. By taking advantage of quantum tunneling effect, local barriers are overcome and better threshold values can be found at the early stage of search process. The new algorithm based on the formalism is demonstrated with benchmark examples of global optimization. The results between the new algorithm and the Grover search method are also compared.

ASME International Design Engineering Technical Conferences and Computers and Information in Engineering Conference (IDETC/CIE)Aug 17, 20148 citations

Grover’s Algorithm for Unstructured Search

Franklin de Lima Marquezino, Renato Portugal, Carlile Lavor

SpringerBriefs in computer scienceJan 1, 20191 citation

Circuit-depth optimization of quantum partial-search algorithms

Yan-Bo Jiang, Xiao-Hui Wang, Kun Zhang +1 more

Grover's algorithm is optimal in terms of oracle queries. We can trade accuracy for speed, which gives rise to the quantum partial-search algorithm. The partial-search algorithm is implemented using two kinds of Grover operators, global and local, where the former is the standard Grover operator for full search and the latter has a diffusion operator acting on the search subspace. The global-local-global sequence, also known as the Grover-Radhakrishnan-Korepin (GRK) algorithm, has been proved optimal in the oracle-query metric. In this work, we show that the alternating sequence of global and local Grover operators, formed by repeatedly applying a fixed product of global and local Grover operators, can achieve a lower expected circuit depth than the GRK algorithm. Through systematic analysis, we obtain its exact success probability, expected depth, and asymptotically optimal parameters. We derive the boundary, characterized by the ratio between the depths of the oracle and the global diffusion operator, separating the depth-optimal and oracle-optimal partial-search algorithms. When the depths of the oracle and the global diffusion operator are comparable, our proposed alternating partial-search sequence can reduce the minimum expected circuit depth by more than 20\% compared with the GRK algorithm.Grover's algorithm is optimal in terms of oracle queries. We can trade accuracy for speed, which gives rise to the quantum partial-search algorithm. The partial-search algorithm is implemented using two kinds of Grover operators, global and local, where the former is the standard Grover operator for full search and the latter has a diffusion operator acting on the search subspace. The global-local-global sequence, also known as the Grover-Radhakrishnan-Korepin (GRK) algorithm, has been proved optimal in the oracle-query metric. In this work, we show that the alternating sequence of global and local Grover operators, formed by repeatedly applying a fixed product of global and local Grover operators, can achieve a lower expected circuit depth than the GRK algorithm. Through systematic analysis, we obtain its exact success probability, expected depth, and asymptotically optimal parameters. We derive the boundary, characterized by the ratio between the depths of the oracle and the global diffusion operator, separating the depth-optimal and oracle-optimal partial-search algorithms. When the depths of the oracle and the global diffusion operator are comparable, our proposed alternating partial-search sequence can reduce the minimum expected circuit depth by more than 20\% compared with the GRK algorithm.

quant-pharXiv:2609.28147Sep 24, 20260 citations

A Grover-based quantum search of optimal order for an unknown number of marked elements

Christof Zalka

We want to find a marked element out of a black box containing N elements. When the number of marked elements is known this can be done elegantly with Grover's algorithm, a variant of which even gives a correct result with certainty. On the other hand, when the number of marked elements is not known the problem becomes more difficult. For every prescribed success probability I give an algorithm consisting of several runs of Grover's algorithm that matches a recent bound by Buhrman and de Wolf on the order of the number of queries to the black box. The improvement in the order over a previously known algorithm is small and the number of queries can clearly still be reduced by a constant factor.We want to find a marked element out of a black box containing N elements. When the number of marked elements is known this can be done elegantly with Grover's algorithm, a variant of which even gives a correct result with certainty. On the other hand, when the number of marked elements is not known the problem becomes more difficult. For every prescribed success probability I give an algorithm consisting of several runs of Grover's algorithm that matches a recent bound by Buhrman and de Wolf on the order of the number of queries to the black box. The improvement in the order over a previously known algorithm is small and the number of queries can clearly still be reduced by a constant factor.

arXiv:quant-ph/9902049Feb 12, 19999 citations

\{ (\langle M \rangle, 1^n, 1^t ) \mid \text{ TM }M\text{ accepts an }x\in\{0,1\}^n\text{ within }t\text{ steps}\}.

t

is large enough, then M accepts each word in

L(M)

with length

n

within

t

steps. So, one can use methods from computability theory to show that black box searching is the fastest way to find a solution. Therefore, Grover's algorithm is optimal for NP-complete problems.