A quantum circuit logical puzzle

I’ve always been a fan of logic puzzles, in which you are given a list of premises (“clues”) and asked to deduce the answer to a given question. In this blog post I’m going to offer you a quantum logic puzzle, or, more accurately, a logic puzzle based on a simple quantum circuit.

The clues:

1. The single-qubit gates denoted by the question marks are I, H, X, and Z, each gate is present in the circuit exactly once.
2. The state generated by this circuit from the |00⟩ state is entangled.
3. Swapping the two gates that act on the bottom qubit changes the state.
4. Swapping the two gates applied after the CNOT gate (on the right side of the circuit) does not change the state but changes its global phase.

What state does this circuit prepare? Is it possible to identify the circuit uniquely from this information?

You had a week to solve the puzzle, and now it is time for the solution! Let’s see how you could solve this puzzle in two different ways.

Solution 1: logical

Clue #2 allows us to identify the position of the H gate right away: for the CNOT gate to entangle the two gates, its control qubit must be in superposition, and of the gates we’re given only the H gate does that.

Now we have 6 possible states to consider: all permutations of the gates I, X, and Z. Clue #3 allows us to narrow down the search space a bit more: both I and X gate commute with the CNOT gate when applied on the target qubit, so if both were acting on the bottom qubit, clue #3 wouldn’t hold. This rules out two more possibilities, leaving us with 4: H – I – X – Z, H – I – Z – X, H – X – I – Z, and H – X – Z – I. (Here I list the gates in the reading order: the top left one, the top right one, the bottom left one, and the top right one.)

After that it’s trial and error: you need to try these four combinations and for each of them check whether clues #3 and #4 fit them. In the end you should have two possible answers: H – I – X – Z and H – X – I – Z. Both these circuits prepare the same state: the Bell state 1/√2 (|10⟩ – |01⟩).

Solution 2: Q# code

Now let’s see if we can verify our pen-and-paper computations with some Q# code. We’ll start with the same deduction as in the previous solution, identifying the location of the H gate, and focus on the other three gates. To check whether a certain circuit satisfies clues #3 and #4, we need several steps:

1. Encode the circuit.

We’ll use a String[] type, with each array element encoding the name of the gate. If we were going to use this type only in Q# code, we could’ve used (Qubit => Unit is Adj+Ctl)[] type, with array elements being the gates themselves, but, as you’ll see later, we’ll need to pass that type from the classical host program, and we can’t do that with callable types.

2. Implement applying the given circuit as a parameterized operation.

We’ll do that using two operations: one operation to apply an individual gate based on its string name

operation ApplyGate (q : Qubit, gateStr : String) : Unit is Adj + Ctl {
    let gate = gateStr == "H" ? H | gateStr == "X" ? X | gateStr == "Z" ? Z | I;
    gate(q);
}

and another to apply the whole circuit:

operation ApplyCircuit (qs : Qubit[], gatesStr : String[]) : Unit is Adj + Ctl {
    ApplyGate(qs[0], gatesStr[0]);
    ApplyGate(qs[1], gatesStr[2]);
    CNOT(qs[0], qs[1]);
    ApplyGate(qs[0], gatesStr[1]);
    ApplyGate(qs[1], gatesStr[3]);
}

3. Test clue #3.

Here we’ll use the same trick for checking states equality that I use in the Quantum Katas: apply the operation that prepares one of the states, apply adjoint of the operation that prepares the other state, and check whether the resulting state is |00⟩ using the library operation AssertAllZero. We’ll use a convenient library function Swapped to swap the elements of the array to represent swapping the gates in the circuit:

operation TestThirdConstraint (gates : String[]) : Unit {
    use qs = Qubit[2];
    ApplyCircuit(qs, gates);
    Adjoint ApplyCircuit(qs, Swapped(2, 3, gates));
    // If the result is not 00, the constraint is satisfied.
    AssertAllZero(qs);
}

However, we’ll need to modify this trick a bit. If we’re going to try all possible gate combinations and check whether each of them fits the clues, we need to be able to figure out whether the states are equal or not programmatically, and Q# doesn’t offer exception handling. Instead, we’ll call this code from a classical host code (in this case C#) and do exception handling there:

var thirdSatisfied = false;
try
{
    TestThirdConstraint.Run(sim, new QArray<string>(gates)).Wait();
}
catch (Exception)
{
    thirdSatisfied = true;
}

4. Test clue #4

We’ll take a similar approach to testing clue #4, though we’ll need to check two parts of the clue here: first, that swapping two gates doesn’t change the state itself, and second, that swapping two gates changes the global phase of the state.

The first part of the check can be done similarly to the TestThirdConstraint operation above. For the second part of the test, we’ll allocate an extra qubit in the |+⟩ state and compare controlled versions of the state preparation operations to coax out the global phase that should be introduced by the gate swap. Furthermore, we can observe that that global phase can only be -1 (the Z gate is the only one that can introduce it), so we can make our test even more accurate: we can check that after applying the controlled versions of both operations the control qubit should end up in the |+⟩ state.

With these observations in place, the test for clue #4 will work as the opposite of the test for clue #3: the clue is satisfied only if the test operation does not throw an exception.

 

With all these pieces assembled and the classical host program iterating over all gate combinations, this solution yields the same result as the pen-and-paper one. You can find the complete code for this puzzle here.

For this puzzle, the advantage of the programmatic solution is not immediately clear – with so few possible circuits, writing the code might take longer than trying all possibilities by hand! However, the code is less error-prone compared to manual computations, and it scales up a lot better than the pen-and-paper approach!