quantum_counting

quantum_counting#

Functionality#

Quantum counting is a quantum algorithm for efficiently counting the number of solutions for a given search problem.

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

\[ f: \{0, 1\}^n \mapsto \{0, 1\} \]
\[\begin{split} f(x) = \begin{cases}1 & \text{if } x \in B \\ 0 & \text{if } x \notin B\end{cases} \end{split}\]

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

Calculate the number of solutions \(M=|f^{-1}(1)| = |B|\) [37].

counting.py#

Callee: QuantumCounting

The quantum circuit of this algorithm is shown below:

quantum counting circuit

Quantum counting circuit (Source: Qiskit/textbook)

Finding the number of solutions \(M\):

Given the decimal integer output of the register \(v\), the number of counting qubits \(t\) and the number of searching qubits \(n\), to get \(\theta\), we need to do:

\[ \theta = v \times \frac{2 \pi}{2^t}. \]

Rememeber that QPE gives a measured value \(v=2^n \phi\) from the eigenvalue \(e^{2\pi i \phi}\). After some derivations detailed in [37] [38] [39], we have:

\[ M = N \sin^2\frac{\theta}{2}. \]

And we can see we have (approximately) the correct answer! We can approximately calculate the error in this answer using:

m = t - 1 # Upper bound: Will be less than this 
err = (math.sqrt(2*M*N) + N/(2**(m+1)))*(2**(-m))
print("Error < %.2f" % err)

Test expectations:

Upon measurement, the basis state \(v\) with the largest probability is used to compute the approximate \(\hat{M}\). The error bound should satisfy \(|M-\hat{M}| \leq \sqrt{2MN}+\frac{N}{2^t}\frac{1}{2^{t-1}}\).

Doc reference: [38] [39]

Code Example#

The following code gives an example to prepare the argument oracle for implementing the GroverOperator class:

Example 1: Quantum circuit from [17]

>>> from qiskit.circuit import QuantumCircuit
>>> from qiskit.circuit.library import GroverOperator
>>> oracle = QuantumCircuit(2)
>>> oracle.z(0)  # good state = first qubit is |1>. Remember this is a phase oracle.
>>> grover_op = GroverOperator(oracle, insert_barriers=True)
>>> grover_op.decompose().draw()
         ┌───┐ ░ ┌───┐ ░ ┌───┐          ┌───┐      ░ ┌───┐
state_0: ┤ Z ├─░─┤ H ├─░─┤ X ├───────■──┤ X ├──────░─┤ H ├
         └───┘ ░ ├───┤ ░ ├───┤┌───┐┌─┴─┐├───┤┌───┐ ░ ├───┤
state_1: ──────░─┤ H ├─░─┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├─░─┤ H ├
               ░ └───┘ ░ └───┘└───┘└───┘└───┘└───┘ ░ └───┘

Example 2: Statevector

>>> from qiskit.quantum_info import Statevector
>>> from qiskit.circuit.library import GroverOperator
>>> oracle_sv = Statevector([0, 0, 0, 1, 0, 0, 0, 0])   # good state = |3>
>>> grover_op = GroverOperator(oracle_sv, insert_barriers=True)
>>> grover_op.decompose().draw()
global phase: π
         ┌─────────────────────────────┐ ░ ┌───┐ ░ ┌───┐          ┌───┐      ░ ┌───┐
state_0: ┤0                            ├─░─┤ H ├─░─┤ X ├───────■──┤ X ├──────░─┤ H ├
         │                             │ ░ ├───┤ ░ ├───┤       │  ├───┤      ░ ├───┤
state_1: ┤1 Diagonal(1,1,1,-1,1,1,1,1) ├─░─┤ H ├─░─┤ X ├───────■──┤ X ├──────░─┤ H ├
         │                             │ ░ ├───┤ ░ ├───┤┌───┐┌─┴─┐├───┤┌───┐ ░ ├───┤
state_2: ┤2                            ├─░─┤ H ├─░─┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├─░─┤ H ├
         └─────────────────────────────┘ ░ └───┘ ░ └───┘└───┘└───┘└───┘└───┘ ░ └───┘

API#

qolumbina.programs.quantum_counting.counting#

class QuantumCounting(oracle, counting_qubits, name=None)[source]#

Bases: QuantumCircuit

Quantum Counting Algorithm Circuit. This class implements the quantum counting algorithm using Grover’s operator and inverse Quantum Fourier Transform (QFT).

Parameters:

  • oracle (QuantumCircuit | Statevector) – The oracle circuit that marks the solutions. This argument derermines the number of searching qubits, i.e., \(n\). Besides, be sure that the oracle is a phase oracle. Otherwise, the algorithm will not work as expected.

  • counting_qubits (int) – The number of counting qubits, i.e., \(t\).

  • name (str | None) – Optional name of the circuit.

Raises:

TypeError – If the oracle is not a QuantumCircuit or Statevector.

grover_operator(n_iterations)[source]#

Grover iteration circuit for oracle :param n_iterations: Number of times to repeat the circuit.

Returns:

Gate that implements n_iterations of the Grover operator

Parameters:

n_iterations (int)

Contents