Playing with Google Cirq (1) — Grover's Search Algorithm

Objective

Following Playing with Qiskit (4) and Playing with cuQuantum (2) — Grover's Search Algorithm, I would like to try running Grover's search algorithm using Google Cirq.

It's not that I have a special attachment to Grover's search algorithm; I'm just using it as a subject for test-driving the framework, so it doesn't have much meaning in itself^[1].

Importing Basic Packages

For now, I'll import the following. If I don't use SVGCircuit, the circuit visualization becomes quite plain, so I'd like to use it.

import numpy as np
import cirq
from cirq.contrib.svg import SVGCircuit
%matplotlib inline

Creating the Oracle

I'm not sure if this is the right way to write it, but using cirq.Moment might be convenient for roughly describing gate actions at the "same time." Also, describing multi-controlled gates is very easy and can be achieved by simply appending .controlled() to a gate. Note that while I used for i, digit in enumerate(state[::-1]): to reverse the order in Qiskit considering the qubit order, it shouldn't be necessary this time... so I'm not doing that. I'm making qubit 0 the MSB.

def revserse_phase(circuit, qubits, state: str):
    n_qubits = len(qubits)
    qr = []
    for i, digit in enumerate(state):
        if digit == '0':
            qr.append(i)

    circuit.append([
        cirq.Moment(*[cirq.X(qubits[i]) for i in qr]),
        # MCZ start (HXH = Z)
        cirq.Z.controlled(n_qubits-1).on(
            *[qubits[i] for i in range(1, n_qubits)], qubits[0]),
        # MCZ end
        cirq.Moment(*[cirq.X(qubits[i]) for i in qr])
    ])

def define_oracle(n_qubits, solutions):
    # Create the oracle
    qubits = cirq.LineQubit.range(n_qubits)
    oracle = cirq.Circuit()

    for sol in solutions:
        revserse_phase(oracle, qubits, sol)

    return oracle

Creating the Diffuser

This can also be written succinctly. It might be quite easy as it can be written with a vibe similar to Sequential in Keras.

def define_diffuser(n_qubits):
    qubits = cirq.LineQubit.range(n_qubits)
    diffuser = cirq.Circuit()
    diffuser.append([
        cirq.Moment(*[cirq.H(qubits[i]) for i in range(n_qubits)]),
        cirq.Moment(*[cirq.X(qubits[i]) for i in range(n_qubits)]),
        # MCZ start (HXH = Z)
        cirq.Z.controlled(n_qubits-1).on(
            *[qubits[i] for i in range(1, n_qubits)], qubits[0]),
        # MCZ end
        cirq.Moment(*[cirq.X(qubits[i]) for i in range(n_qubits)]),
        cirq.Moment(*[cirq.H(qubits[i]) for i in range(n_qubits)])
    ])

    return diffuser

Trying with 5 Qubits!

In this problem, I've again set the solutions as two 5-digit binary numbers: 00101 and 11111. First, I'll perform the standard circuit visualization.

n_qubits = 5
solutions = ['00101', '11111']

oracle = define_oracle(n_qubits, solutions)
SVGCircuit(oracle)

If you're used to Qiskit, it looks quite plain, but well, that's not essential, so I won't worry about it.

diffuser = define_diffuser(n_qubits)
SVGCircuit(diffuser)

It seems to be exactly as intended.

Solving the Problem

N = 2**n_qubits
angle = np.arcsin(np.sqrt(len(solutions) / N))
counts = int((np.pi/2 - angle) / (2*angle) + 0.5)
print(f'{angle=}, {np.pi/2=}, {counts=}')

angle=0.25268025514207865, np.pi/2=1.5707963267948966, counts=3

So, after repeating the quantum amplitude amplification about 3 times, the probability amplitude corresponding to the solution should be maximized.

qubits = cirq.LineQubit.range(n_qubits)
grover = cirq.Circuit()
# initialize |s>
grover.append([
    cirq.Moment(*[cirq.H(qubits[i]) for i in range(n_qubits)])
])
for _ in range(counts):
    grover += oracle
    grover += diffuser
SVGCircuit(grover)

Well, something like this...

Using the qsim Simulator

According to qsim:

Optimized quantum circuit simulators

qsim
qsim is a full wave function simulator written in C++. It uses gate fusion, AVX/FMA vectorized instructions and multi-threading using OpenMP to achieve state of the art simulations of quantum circuits. qsim is integrated with Cirq and can be used to run simulations of up to 40 qubits on a 90 core Intel Xeon workstation.

So, it seems to be an optimized and powerful simulator. I'll use it this time. Although I'm not sure if it will be in the next post, I have an aim to connect it to cuQuantum from GPU-based quantum simulation visible in the left pane of Get started with qsimcirq.

import qsimcirq
import matplotlib.pyplot as plt

def binary_labels(num_qubits):
    return [bin(x)[2:].zfill(num_qubits) for x in range(2 ** num_qubits)]

qubits = cirq.LineQubit.range(n_qubits)
grover.append(cirq.measure(qubits[:]))

simulator = qsimcirq.QSimSimulator()
result = simulator.run(grover, repetitions=1000)
# To view it as probability, you can do the following.
#result = cirq.get_state_histogram(result)
#result = result / np.sum(result)
_ = cirq.plot_state_histogram(
    result, plt.subplot(), title = 'Measurement results',
    xlabel = 'State', ylabel = 'Count',
    tick_label=binary_labels(n_qubits))
plt.xticks(rotation=70)
plt.show()

I tried to make the output look somewhat like Qiskit. From this figure, you can see that the probability amplitudes for the solutions 00101 and 11111 have become extremely large.

Summary

I have briefly explored running Grover's search algorithm using Cirq. It feels somewhat like Keras overall; instead of adding gates by calling methods on the circuit as in Qiskit or Blueqat, it seems to be more about creating gates and appending them like layers in a deep learning model. I think this is a matter of perspective, so it's fine to just switch your mental model as needed.

脚注

1. Note that since this is only my second day using Cirq, I'm not sure if I'm writing it in the best way...