Quantum Counting

Quantum Counting is a simple quantum algorithms which consists in performing a phase estimation on a Grover amplification.

The method qat.lang.algorithms.quantum_counting can produce a routine performing a counting directly from an oracle.

Let us use it to count the number of repetitions in the set of all bitstrings of length $2k$. We will use exactly the same oracle as in this notebook.

from qat.lang.algorithms import quantum_counting
from qat.lang.AQASM import QRoutine, QInt, build_gate

@build_gate('ORACLE', [int], arity=lambda a: 2 * a)
def detect_repetitions(k):
    routine = QRoutine()
    first_half = routine.new_wires(k, QInt)
    second_half = routine.new_wires(k, QInt)
    (first_half == second_half).phase()
    return routine

counting = quantum_counting(detect_repetitions(3), 3)
counting.display()

As you can see, generating the quantum counting routine is quite straightforward.

Let's simulate it !

We will define a program and declare the phase register as a Quantum Integer (to facilitate the conversion of the phase to an integer).

Moreover, we will define a method guess_count that perform the necessary computations to translate the measured phase into a count.

import numpy as np
from qat.qpus import get_default_qpu
from qat.lang.AQASM import Program, QInt
qpu = get_default_qpu()


def guess_count(theta, nbits):
    guess = np.round(np.sin(theta / 2) ** 2 * (1 << nbits))
    if guess > (1 << (nbits - 1)):
        return (1 << nbits) - guess
    return guess

# The length of the bitstrings will be 2 * width
width = 3
# This is the number of precision bits used in the phase estimation
nbits = 7

prog = Program()
data = prog.qalloc(2 * width)
# declaring the phase register as an integer
phase = prog.qalloc(nbits, QInt)

counting = quantum_counting(detect_repetitions(width), nbits)
counting(data, phase)
# Measuring only the phase register and only once !
result = qpu.submit(prog.to_circ().to_job(qubits=[phase], nbshots=1))
print("Expected count:", 1 << width)
for sample in result:
    print("Measured count:", guess_count(2 * np.pi * sample.state.value[0] / (1 << nbits), 2 * width))

Expected count: 8
Measured count: 8.0

This program should (with high probability) returns the correct estimate of the solution count.