Using Qmod’s Quantum Conditionals in Grover’s Algorithm

In Qmod, the ‘control’ statement is analogous to a classical ‘if’ statement in itsstructure, with an arbitrary Boolean expression as its condition, a statementblock, and optionally an ‘else’ block. Of course, unlike a classical ‘if’, the condition is implemented reversibly and acts coherently, soboth the predicate and the controlled operations apply across a superpositionof states. In thisblog post, we look at how ‘control’ statements directly express the algorithmicintent 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, knownas the diffuser operator. You have probably seen the implementation of thesereflection operators in terms of “phase kickback”, using an ancilla qubit inthe minus state. And you may have been a little puzzled by it, as thislow-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 expressionover 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 seethat 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 asimple problem – finding assignments to variables a, b, and cthat 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 (inthis 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]),
        )
    )

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.

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

‍

‍