Grover's Algorithm: Searching a 4-Bit State Space

// Grover's Algorithm
//
// Searches a 4-bit state space (2x2 binary grid) using Grover iterations,
// where r = [a, b, c, d].
//
// The oracle marks the two valid solutions satisfying the constraints:
// a != b, c != d, a != c, and b != d.
// The solutions are [1,0,0,1] and [0,1,1,0].

OPENQASM 3.0;

gate x q { U(pi, 0, pi) q; }
gate h q { U(pi/2.0, 0, pi) q; }
gate cx q0, q1 { ctrl @ U(pi, 0, pi) q0, q1; }
gate xor q0, q1, q2 { cx q0, q2; cx q1, q2; }
gate cccz c0, c1, c2, t { ctrl(3) @ U(0, 0, pi) c0, c1, c2, t; }
gate ccccx c0, c1, c2, c3, t { ctrl(4) @ U(pi, 0, pi) c0, c1, c2, c3, t; }

def oracle(qubit[4] r, qubit[4] s, qubit a) {
    xor r[0], r[1], s[0];
    xor r[2], r[3], s[1];
    xor r[0], r[2], s[2];
    xor r[1], r[3], s[3];

    ccccx s[0], s[1], s[2], s[3], a;

    xor r[1], r[3], s[3];
    xor r[0], r[2], s[2];
    xor r[2], r[3], s[1];
    xor r[0], r[1], s[0];
}

def diffuser(qubit[4] r) {
    h r;
    x r;
    cccz r[0], r[1], r[2], r[3];
    x r;
    h r;
}

def G(qubit[4] r, qubit[4] s, qubit a) {
    oracle(r, s, a);
    diffuser(r);
}

const int n = 4;
qubit[n] r;
qubit[4] s;
qubit a;

reset r;
reset s;
reset a;

h r;
x a;
h a;

int N = 2**n;
int M = 2;
int R = int(pi/4 * sqrt(float(N)/float(M)));

for int i in [0:R-1] {
    G(r, s, a);
}

measure s;
measure a;

xor r[0], r[1], s[0]   →  s[0] = a XOR b  (is a ≠ b ?)
xor r[2], r[3], s[1]   →  s[1] = c XOR d  (is c ≠ d ?)
xor r[0], r[2], s[2]   →  s[2] = a XOR c  (is a ≠ c ?)
xor r[1], r[3], s[3]   →  s[3] = b XOR d  (is b ≠ d ?)

h r     →  transform to uniform superposition basis
x r     →  flip so |11...1⟩ is the state to phase-flip
cccz    →  apply −1 phase to |1111⟩ only
x r     →  undo the flip
h r     →  transform back

N = 2^4 = 16   (search space size)
M = 2          (number of solutions)
R = floor(pi/4 * sqrt(N/M)) = floor(pi/4 * sqrt(8)) ≈ floor(2.22) = 2