Quantum counting algorithm

Short description: Quantum algorithm for counting solutions to search problems

The Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.

Counting problems are common in diverse fields such as statistical estimation, statistical physics, networking, etc. As for quantum computing, the ability to perform quantum counting efficiently is needed in order to use Grover's search algorithm (because running Grover's search algorithm requires knowing how many solutions exist). Moreover, this algorithm solves the quantum existence problem (namely, deciding whether any solution exists) as a special case.

The algorithm was devised by Gilles Brassard, Peter Høyer and Alain Tapp in 1998.

## Contents

* 1 The problem
* 1.1 Classical solution
* 2 The algorithm
* 2.1 Setup
* 2.2 Create superposition
* 2.3 Grover operator
* 2.4 Estimating the value of θ
* 2.5 Analysis
* 3 Uses
* 3.1 Grover's search algorithm for an initially-unknown number of solutions
* 3.2 Speeding up NP-complete problems
* 3.3 Quantum existence problem
* 3.4 Quantum relation testing problem
* 4 See also
* 5 References

## The problem

Consider a finite set {0,1}n of size N=2n and a set B of "solutions" (that is a subset of {0,1}n). Define:

{f:{0,1}n->{0,1}f(x)={1x∈B0x∉B

In other words, f is the indicator function of B.

Calculate the number of solutions M=|f−1(1)|=|B|.[1]

### Classical solution

Without any prior knowledge on the set of solutions B (or the structure of the function f), a classical deterministic solution cannot perform better than Ω(N), because all the N elements of {0,1}n must be inspected (consider a case where the last element to be inspected is a solution).

## The algorithm

Quantum counting circuit

### Setup

The input consists of two registers (namely, two parts): the upper p qubits comprise the first register, and the lower n qubits are the second register.

### Create superposition

The initial state of the system is |0⟩⊗p|0⟩⊗n. After applying multiple bit Hadamard gate operation on each of the registers separately, the state of the first register is

12p/2(|0⟩+|1⟩)⊗p

and the state of the second register is

12n/2(|0⟩+|1⟩)⊗n=1N∑x=0N−1|x⟩

an equal superposition state in the computational basis.

### Grover operator

Because the size of the space is |{0,1}n|=2n=N and the number of solutions is |B|=M, we can define the normalized states:[2]: 252

|α⟩=1N−M∑x∉B|x⟩,and|β⟩=1M∑x∈B|x⟩.

Note that

N−MN|α⟩+MN|β⟩=1N∑x=0N−1|x⟩,

which is the state of the second register after the Hadamard transform.

Geometric visualization of Grover's algorithm shows that in the two-dimensional space spanned by |α⟩ and |β⟩, the Grover operator is a counterclockwise rotation; hence, it can be expressed as

G=[cos⁡θ−sin⁡θsin⁡θcos⁡θ]

in the orthonormal basis {|α⟩,|β⟩}.[2]: 252 [3]: 149

From the properties of rotation matrices we know that G is a unitary matrix with the two eigenvalues e±iθ.[2]: 253

### Estimating the value of θ

From here onwards, we follow the quantum phase estimation algorithm scheme: we apply controlled Grover operations followed by inverse quantum Fourier transform; and according to the analysis, we will find the best p-bit approximation to the real number θ (belonging to the eigenvalues e±iθ of the Grover operator) with probability higher than 4π2.[4]: 348 [3]: 157

Note that the second register is actually in a superposition of the eigenvectors of the Grover operator (while in the original quantum phase estimation algorithm, the second register is the required eigenvector). This means that with some probability, we approximate θ, and with some probability, we approximate 2π−θ; those two approximations are equivalent.[2]: 224–225

### Analysis

Assuming that the size N of the space is at least twice the number of solutions (namely, assuming that M≤N2), a result of the analysis of Grover's algorithm is:[2]: 254

sin⁡θ2=MN.

Thus, if we find θ, we can also find the value of M (because N is known).

The error

|ΔM|N=|sin2(θ+Δθ2)−sin2(θ2)|

is determined by the error within estimation of the value of θ. The quantum phase estimation algorithm finds, with high probability, the best p-bit approximation of θ; this means that if p is large enough, we will have Δθ≈0, hence |ΔM|≈0.[2]: 263

## Uses

### Grover's search algorithm for an initially-unknown number of solutions

In Grover's search algorithm, the number of iterations that should be done is π4NM.[2]: 254 [3]: 150

Thus, if N is known and M is calculated by the quantum counting algorithm, the number of iterations for Grover's algorithm is easily calculated.

### Speeding up NP-complete problems

The quantum counting algorithm can be used to speed up solution to problems which are NP-complete.

An example of an NP-complete problem is the Hamiltonian cycle problem, which is the problem of determining whether a graph G=(V,E) has a Hamiltonian cycle.

A simple solution to the Hamiltonian cycle problem is checking, for each ordering of the vertices of G, whether it is a Hamiltonian cycle or not. Searching through all the possible orderings of the graph's vertices can be done with quantum counting followed by Grover's algorithm, achieving a speedup of the square root, similar to Grover's algorithm.[2]: 264 This approach finds a Hamiltonian cycle (if exists); for determining whether a Hamiltonian cycle exists, the quantum counting algorithm itself is sufficient (and even the quantum existence algorithm, described below, is sufficient).

### Quantum existence problem

Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of M, but we only wish to know whether M≠0 or not.[5]: 147

A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields M, so by checking whether M≠0 we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of M. Quantum phase estimation can be optimized to eliminate this overhead.[5]: 148

If you are not interested in the control of error probability then using a setup with small number of qubits in the upper register will not produce an accurate estimation of the value of θ, but will suffice to determine whether M equals zero or not.[2]: 263

### Quantum relation testing problem

Quantum relation testing QRT(value,relation). is an extension of quantum existence testing, it decides whether at least one entry can be found in the data base which fulfils the relation to a certain reference value. [6] E.g. QRT(5,>) gives back YES if the data base contains any value larger than 5 else it returns NO. Quantum relation testing combined with classical logarithmic search forms an efficient quantum min/max searching algorithm. [5]: 152 [7]

## See also

* Quantum phase estimation algorithm
* Grover's algorithm
* Counting problem (complexity)

## References

1. ↑ Brassard, Gilles; HØyer, Peter; Tapp, Alain (1998), Larsen, Kim G.; Skyum, Sven; Winskel, Glynn, eds., "Quantum counting", Automata, Languages and Programming (Berlin, Heidelberg: Springer Berlin Heidelberg) 1443: pp. 820–831, doi:10.1007/bfb0055105, ISBN 978-3-540-64781-2, http://link.springer.com/10.1007/BFb0055105, retrieved 2024-10-16
2. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Chuang, Michael A. Nielsen & Isaac L. (2001). Quantum computation and quantum information (Repr. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN 978-0521635035.
3. ↑ 3.0 3.1 3.2 Benenti, Guiliano; Strini, Giulio Casati, Giuliano (2004). Principles of quantum computation and information (Reprinted. ed.). New Jersey [u.a.]: World Scientific. ISBN 978-9812388582.
4. ↑ Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (8 January 1998). "Quantum algorithms revisited". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 454 (1969): 339–354. doi:10.1098/rspa.1998.0164. Bibcode: 1998RSPSA.454..339C.
5. ↑ 5.0 5.1 5.2 Imre, Sandor; Balazs, Ferenc (January 2005). Quantum Computing and Communications - An Engineering Approach. Wiley. ISBN 978-0470869024.
6. ↑ Elgaily, Sara; Imre, Sandor (2021). "Constrained Quantum Optimization for Resource Distribution Management". International Journal of Advanced Computer Science and Applications 12 (8).
7. ↑ Imre, Sandor (2007). "Quantum Existence Testing and its Application for Finding Extreme Values in Unsorted Databases". IEEE Transactions on Computers 56 (5): 706–710. doi:10.1109/TC.2007.1032.

* v
* t
* e

Quantum information science

General|

* Quantum computing
* Qubit
* physical vs. logical
* DiVincenzo's criteria
* Quantum information
* Quantum programming
* Quantum processors
* Cloud-based quantum computing
* Timeline of quantum computing

Theorems|

* Bell's theorem
* Gleason's theorem
* Gottesman–Knill theorem
* Holevo's theorem
* Margolus–Levitin theorem
* No-broadcast theorem
* No-cloning theorem
* No-communication theorem
* No-deleting theorem
* No-hiding theorem
* No-teleportation theorem
* PBR theorem
* Quantum threshold theorem

Quantum
communication|

* Quantum capacity
* Classical capacity
* Entanglement-assisted classical capacity
* Quantum channel
* Quantum network
* Quantum cryptography
* Quantum key distribution
* BB84
* SARG04
* Three-stage quantum cryptography protocol
* Quantum teleportation
* Superdense coding
* LOCC
* Entanglement distillation

Quantum algorithms|

* Universal quantum simulator
* Deutsch–Jozsa algorithm
* Grover's algorithm
* Quantum Fourier transform
* Shor's algorithm
* Simon's problem
* Quantum phase estimation algorithm
* Quantum counting algorithm
* Quantum annealing
* Quantum algorithm for linear systems of equations
* Amplitude amplification

Quantum
complexity theory|

* Quantum Turing machine
* EQP
* BQP
* QMA
* PostBQP
* QIP

Quantum
computing models|

* Quantum circuit
* Quantum logic gate
* One-way quantum computer
* cluster state
* Adiabatic quantum computation
* Topological quantum computer

Quantum
error correction|

* Stabilizer codes
* Entanglement-Assisted Quantum Error Correction
* Shor code
* Steane code
* CSS code
* Quantum convolutional codes
* Toric code

Physical
implementations|

| Quantum optics|

* Cavity QED
* Circuit QED
* Linear optical quantum computing
* KLM protocol
* Boson sampling

|

Ultracold atoms|

* Trapped ion quantum computer
* Optical lattice

Spin-based|

* Nuclear magnetic resonance QC
* Kane QC
* Loss–DiVincenzo QC
* Nitrogen-vacancy center

Superconducting
quantum computing|

* Charge qubit
* Flux qubit
* Phase qubit
* Transmon

Software|

* libquantum
* OpenQASM
* Q#
* Qiskit
* IBM Q Experience

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Quantum counting algorithm. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Quantum_counting_algorithm&oldid=4152678"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template