Using Qmod’s Quantum Conditionals in Grover’s Algorithm

In Qmod, the ‘control’ statement is analogous to a classical ‘if’ statement in its structure, with an arbitrary Boolean expression as its condition, a statement block, and optionally an ‘else’ block. Of course, unlike a classical ‘if’, the condition is implemented reversibly and acts coherently, so both the predicate and the controlled operations apply across a superposition of states. In this blog post, we look at how ‘control’ statements directly express the algorithmic intent in a familiar context.

Grover’s famous search algorithm alternates two reflections – one about the “good” states, known as the phase oracle, and the other about the initial (mean) state, known as the diffuser operator. You have probably seen the implementation of these reflection operators in terms of “phase kickback”, using an ancilla qubit in the minus state. And you may have been a little puzzled by it, as this low-level “trick” obscures the algorithmic intent.

In Qmod, shifting the phase of some states relative to others can be expressed by applying the ‘phase’ statement conditionally, where the condition is a Boolean expression over quantum variables. Let’s consider a very simple example first. Here, we apply a fixed phase shift to states that satisfy a simple Boolean condition:

@qfunc
def main(qarr: Output[QArray[QBit, 2]]):
    allocate(qarr)
    hadamard_transform(qarr)
    control(qarr[0] & ~qarr[1], lambda: phase(pi / 4))

We can obtain the resulting state vector by simulating this program. We then see that all components of the state vector have equal magnitude, but the phase of [1,0] is shifted by π/4 relative to the others. And indeed, this is the only one that satisfies the condition in our ‘control’ statement:

    qarr           amplitude magnitude  phase  probability bitstring
0  [1, 1]  0.000000+0.500000j      0.50  0.50π         0.25        11
1  [1, 0] -0.353553+0.353553j      0.50  0.75π         0.25        01
2  [0, 1]  0.000000+0.500000j      0.50  0.50π         0.25        10
3  [0, 0] -0.000000+0.500000j      0.50  0.50π         0.25        00

Relative phases cannot be directly observed in real quantum hardware. But they play a key role in quantum algorithms by orchestrating interference effects, as is the case in Grover’s algorithm.

Consider a simple problem – finding assignments to variables a, b, and c that satisfy the equation a + 2*b + 3*c == 10. To apply Grover’s algorithm, we need to come up with a phase oracle – a quantum subroutine that flips the phase of the sought-after states. As we’ve seen, using the ‘control’ statement makes this trivial. The harder task of synthesizing the expression into an efficient gate-level implementation is left to the Qmod compiler.

@qfunc
def phase_oracle(a: QNum, b: QNum, c: QNum):
    control(
        a + 2 * b + 3 * c == 10,
        lambda: phase(pi)
    )

Grover’s diffuser operator reflects the state about the uniform superposition. This can be implemented by conjugating a selective phase flip about the ∣0⟩ state with Hadamard transforms:

@qfunc
def grover_diffuser(state: QNum) -> None:
    within_apply(
        lambda: hadamard_transform(state),
        lambda: control(state != 0, lambda: phase(pi))
    )

We can implement Grover’s search using the above building blocks by putting the state in a uniform superposition of all computational states and alternating the oracle and diffuser operators the appropriate number of iterations. This is the full code, assuming a, b, and c are non-negative 2-bit integers (in this small search space, two iterations suffice):

@qfunc
def main(a: Output[QNum[2]], b: Output[QNum[2]], c: Output[QNum[2]]):
    allocate(a)
    allocate(b)
    allocate(c)
    hadamard_transform([a, b, c])
    power(NUM_ITERATIONS,
        lambda: (
            phase_oracle(a, b, c),
            grover_diffuser([a, b, c]),
        )
    )

Executing this program with 1000 shots on a simulator, we see that the states satisfying our equation are sampled with very high probability, while the others occur with near-zero probability:

    a  b  c  counts  probability bitstring
0   3  2  1     199        0.199    011011
1   1  0  3     198        0.198    110001
2   2  1  2     197        0.197    100110
3   1  3  1     195        0.195    011101
4   0  2  2     188        0.188    101000
5   0  3  1       2        0.002    011100
6   3  3  2       2        0.002    101111
7   1  0  0       1        0.001    000001
...

The double reflection pattern in the Grover iteration operator is used in a wide range of applications, well beyond unstructured search, including amplitude amplification, quantum walks, and amplitude estimation. More generally, applying operations conditionally, where the condition is expressed as an arithmetic or Boolean expression over computational basis states, is the natural way to capture the intent of many applications and higher-level building blocks. This concise syntax for quantum conditionals does not come at the expense of efficiency; the compiler generates a highly optimized gate-level implementation that computes (and uncomputes) the condition.

For more details and examples of the Qmod ‘control’ and ‘phase’ statements, see the Qmod language reference.