This paper extends the quantum search class of algorithms to the multiple solution case. It is shown that, like the basic search algorithm, these too can be represented as a rotation in an appropriately defined two dimensional vector space. This yields new applications - an algorithm is presented that can create an arbitrarily specified quantum superposition on a space of size N in O(sqrt(N)) steps. By making a measurement on this superposition, it is possible to obtain a sample according to an arbitrarily specified classical probability distribution in O(sqrt(N)) steps. A classical algorithm would need O(N) steps.This paper extends the quantum search class of algorithms to the multiple solution case. It is shown that, like the basic search algorithm, these too can be represented as a rotation in an appropriately defined two dimensional vector space. This yields new applications - an algorithm is presented that can create an arbitrarily specified quantum superposition on a space of size N in O(sqrt(N)) steps. By making a measurement on this superposition, it is possible to obtain a sample according to an arbitrarily specified classical probability distribution in O(sqrt(N)) steps. A classical algorithm would need O(N) steps.

arXiv:quant-ph/9912001Dec 1, 199923 citations

Synthesis of Quantum Superpositions by Quantum Computation

Lov K. Grover

The quantum search algorithm can be looked at as a technique for synthesizing a particular kind of superposition-one whose amplitude is concentrated in a single basis state. This basis state is defined by a binary function f(&xmacr;) that is nonzero in this desired basis state and zero everywhere else. This paper extends the quantum search algorithm to an algorithm that can create an arbitrarily specified superposition on a space of size N in O(sqrt[N] ) steps. The superposition is specified by a complex valued function f(&xmacr;) that specifies the desired amplitude of the system in basis state &xmacr;.The quantum search algorithm can be looked at as a technique for synthesizing a particular kind of superposition-one whose amplitude is concentrated in a single basis state. This basis state is defined by a binary function f(&xmacr;) that is nonzero in this desired basis state and zero everywhere else. This paper extends the quantum search algorithm to an algorithm that can create an arbitrarily specified superposition on a space of size N in O(sqrt[N] ) steps. The superposition is specified by a complex valued function f(&xmacr;) that specifies the desired amplitude of the system in basis state &xmacr;.

Physical Review LettersAug 7, 2000120 citations

An extention of Grover's quantum search algorithm (Foundations of Computer Science)

Keisuke Tanaka

Quantum computers and their algorithm are now widely studied.We consider the prob- lem of making a superposition with an arbitrarily specified amplitudes.By modifying Grover's quantum search algorithm, we show that this can be done in time $O(\sqrt{N})$ with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where $N=2^{n}$ , the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is $\Omega(N)$ .By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in $O(\sqrt{N})$ time.Quantum computers and their algorithm are now widely studied.We consider the prob- lem of making a superposition with an arbitrarily specified amplitudes.By modifying Grover's quantum search algorithm, we show that this can be done in time $O(\sqrt{N})$ with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where $N=2^{n}$ , the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is $\Omega(N)$ .By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in $O(\sqrt{N})$ time.

数理解析研究所講究録Apr 1, 20000 citations

Quantum-Inspired Search Algorithms for Combinatorial Optimization

Jincheng Zhang

This paper explores the application of quantum-inspired concepts to the field of combinatorial optimization. Traditional search algorithms often struggle with the complexity of problems involving numerous possible solutions. We propose a novel approach that leverages the principles of quantum superposition and interference, albeit within a classical computing framework, to enhance the efficiency of search processes. The core of our method involves a hybrid algorithm that combines established classical search techniques with probabilistic sampling strategies informed by quantum mechanics. We aim to demonstrate that by mimicking these quantum phenomena, we can significantly improve the speed and effectiveness of solving complex combinatorial optimization problems. The algorithm's performance is evaluated through theoretical analysis and conceptual design, focusing on the potential for achieving performance gains without requiring actual quantum hardware. The key contribution lies in the strategic application of probabilistic sampling to explore solution spaces in a manner analogous to quantum superposition, followed by interference-like mechanisms to guide the search towards promising regions. This approach represents a new direction in optimization, bridging the gap between classical and quantum computing paradigms.This paper explores the application of quantum-inspired concepts to the field of combinatorial optimization. Traditional search algorithms often struggle with the complexity of problems involving numerous possible solutions. We propose a novel approach that leverages the principles of quantum superposition and interference, albeit within a classical computing framework, to enhance the efficiency of search processes. The core of our method involves a hybrid algorithm that combines established classical search techniques with probabilistic sampling strategies informed by quantum mechanics. We aim to demonstrate that by mimicking these quantum phenomena, we can significantly improve the speed and effectiveness of solving complex combinatorial optimization problems. The algorithm's performance is evaluated through theoretical analysis and conceptual design, focusing on the potential for achieving performance gains without requiring actual quantum hardware. The key contribution lies in the strategic application of probabilistic sampling to explore solution spaces in a manner analogous to quantum superposition, followed by interference-like mechanisms to guide the search towards promising regions. This approach represents a new direction in optimization, bridging the gap between classical and quantum computing paradigms.

Aug 28, 20260 citations

From coupled pendulums to quantum search

Lov K. Grover, Anirvan M. Sengupta

Abstract Quantum search is a quantum mechanical technique for searching N possibilities in only √ N steps. There are several diﬀerent perspectives from which one can get to the algorithm - Schro¨dinger’s equation, antenna array, rotation in a two-dimensional Hilbert space, just to name a few. This paper gives a fresh perspective on the algorithm in terms of classical coupled oscillators. Consider N oscillators, one of which is of a diﬀerent resonant frequency. We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles. We show how, by coupling the oscillators together in a very simple way, it is possible to identify the diﬀerent one in only √ N cycles. In case there are multiple oscillators of a diﬀerent frequency, we can estimate the number of these in a time which is the square-root of that required by the sampling method. An extension of this technique to the quantum case leads to the quantum search and some novel algorithms.Abstract Quantum search is a quantum mechanical technique for searching N possibilities in only √ N steps. There are several diﬀerent perspectives from which one can get to the algorithm - Schro¨dinger’s equation, antenna array, rotation in a two-dimensional Hilbert space, just to name a few. This paper gives a fresh perspective on the algorithm in terms of classical coupled oscillators. Consider N oscillators, one of which is of a diﬀerent resonant frequency. We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles. We show how, by coupling the oscillators together in a very simple way, it is possible to identify the diﬀerent one in only √ N cycles. In case there are multiple oscillators of a diﬀerent frequency, we can estimate the number of these in a time which is the square-root of that required by the sampling method. An extension of this technique to the quantum case leads to the quantum search and some novel algorithms.

Chapman & Hall/CRC eBooksFeb 14, 20028 citations

From coupled pendulums to quantum search

Lov K. Grover, Anirvan M. Sengupta

Quantum search is a quantum mechanical technique for searching N possibilities in only √ N steps.There are several different perspectives from which one can get to the algorithm -Schrodinger's equation, antenna array, rotation in a two-dimensional Hilbert space, just to name a few.This paper gives a fresh perspective on the algorithm in terms of a resonance phenomenon which is implemented through classical coupled oscillators.Consider N oscillators, one of which is of a different resonant frequency.We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles.We show how, by coupling the oscillators together in a very simple way, it is possible to identify the different one in only √ N cycles.In case there are multiple oscillators of a different frequency, we can estimate the number of these in a time which is the square-root of that required by the sampling method.An extension of this technique to the quantum case leads to the quantum search & some novel algorithms.Quantum search is a quantum mechanical technique for searching N possibilities in only √ N steps.There are several different perspectives from which one can get to the algorithm -Schrodinger's equation, antenna array, rotation in a two-dimensional Hilbert space, just to name a few.This paper gives a fresh perspective on the algorithm in terms of a resonance phenomenon which is implemented through classical coupled oscillators.Consider N oscillators, one of which is of a different resonant frequency.We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles.We show how, by coupling the oscillators together in a very simple way, it is possible to identify the different one in only √ N cycles.In case there are multiple oscillators of a different frequency, we can estimate the number of these in a time which is the square-root of that required by the sampling method.An extension of this technique to the quantum case leads to the quantum search & some novel algorithms.

Computational matematics series/Computational mathematics seriesFeb 14, 20022 citations

O(\sqrt{N})

with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where

N=2^{n}

, the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is

\Omega(N)

.By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in

O(\sqrt{N})

time.