I was invited to solve a quantum circuit puzzle by Quantum Intuition (@explore_quantum). And, although the goal was simply to solve the puzzle, I felt that my solution was not intuitive; it worked, but it wasn’t clear to me why it worked. Therefore, I proceeded to reverse engineer the puzzle’s black box, after which my solution finally became intuitive.
By the way, I encourage everyone to check out the Quantum Intuition YouTube channel and subscribe.
This is what I found when I tapped on the link provided to me by Quantum Intuition: input states on the far left, a black box after the input states, and, on the far right, the probabilities of measuring 0 in the z basis. The goal of the puzzle was to “turn off” the three qubits by getting all of them to measure 0 with a probability of 1.
I recorded an 11-minute video explaining how I solved the puzzle, as well as how I made sense of the solution by reverse engineering the black box. I didn’t explain how I actually reverse engineered the black box, however, which is why I am going through that particular thought process in this article.
The important takeaway from the video — how I solved the puzzle — is that there was little-to-no intuition involved in discovering the Fredkin and CNOT gates. Discovering the single-qubit gates was fairly intuitive, after discovering the multi-qubit gates, but discovering the multi-qubit gates involved trial-and-error and process-of-elimination rather than deliberation and reasoning. The Fredkin gate, in particular, was attempted after seemingly exhausting every other possibility, which I characterized in the video as more desperation than intuition; there was simply nothing else to try.
the black box revealed
Reverse engineering a black box is easier than it might sound. In fact, it is much like solving a circuit puzzle such as the one presented to me. However, it was actually faster for me to solve the black box than it was for me to solve the puzzle.
- Recreate the circuit
I used Quirk to recreate the circuit with the input states and the solution, but without the black box. I normally prefer to use IBM Q for everything quantum, but Quirk is much faster for this sort of exercise. In Quirk, you can move around and change gates with immediate feedback. In fact, you can grab a gate and just wave it up and down across the circuit to see how that particular gate would affect each of the outputs.
2. Keep it simple
I initially thought the black box might only contain single-qubit operations. This was a puzzle, so that was not the case, but black boxes normally exist to perform a specfic function, not to deliberately confuse those who dare peek inside the mysterious oracle.
In fact, single-qubit operations satisfy the top and bottom qubits. Assuming the Fredkin gate serves an actual purpose, the top and bottom states are swapped mid-way through the circuit. If the top qubit has a Hadamard gate applied inside the black box, it will swap down to the bottom, get cancelled out by the Hadamard gate there, and return to the |0> state, the “off” state. And if the bottom qubit has a pi/2 y rotation applied to it inside the black box, it will cancel the -pi/2 y rotation of the input state and swap |0> to the top. The |1> in the middle will then cause the CNOT to flip the top |0 > to |1>, and then the final NOT gate will flip that |1> right back to |0>, the “off” state.
This provided a glimmer of hope that solving the middle qubit might be easy. Alas, there was no way to solve the middle qubit with a single-qubit operation. If a |1> passes through the black box intact, it causes the Fredkin gate to swap the top and bottom states and the CNOT to bit flip the top qubit, but then the final pi/2 x rotation would leave it showing only a 50% probability of measuring 0, not 100%. Rotating the middle qubit not only doesn’t turn it “off,” it also prevents the top and bottom qubits from turning off.
3. Add sophistication
When single-qubit gates wouldn’t solve the middle qubit, I suspected that a second Fredkin gate might be the culprit. I also suspected that I would need either a pi/2 or -pi/2 x rotation to cancel that final pi/2 x rotation, but I wasn’t initially sure which order to place them in.
After juggling the second Fredkin gate and the rotations around for a bit, I considered building a mirror image of the solution. This turned out to be the real solution to the puzzle, but I am getting ahead of myself. Once I placed a Fredkin gate immediately before the solution’s Fredkin gate and the CNOT immediately before that, the remaining single-qubit operations were intuitive.
4. Fine-tune the results
With the two Fredkin gates and the two CNOTs all cancelling each other out, I was left with intuitive single-qubit operations. The top |0> showed as “on,” therefore a NOT inside the black box flips the |0> to |1>, the final NOT flips the |1> back to |0>, and the top qubit shows as “off.” The bottom qubit starts at |-> and rotates around the z axis to |+> inside the black box. This is the equivalent of starting at |0> and applying a Hadamard gate — which rotates |0> to |+> — which means that the Hadamard gate in the solution rotates the bottom qubit from |+> right back to |0>, which shows as “off.”
The middle qubit, which initially looked like the easiest of the three back when solving the puzzle, turned out to be the tricky one. It starts at |1> and rotates pi/2 around the x axis. This means that it has a 50% probability of being a 0 and a 50% probability of being a 1. If the middle qubit is a 0, both CNOTs and both Fredkin gates do absolutely nothing. If the middle qubit is a 1, it flips the top |1> to |0>, swaps the top and bottom states, swaps the top and bottom states right back again, and then flips the top |0> right back to |1>; you can follow along as the multi-qubit gates cancel each other out. Finally, the second pi/2 x rotation completes the middle qubit’s rotation back to |0 >, and it finally shows as “off.” If that last part isn’t clear: the middle qubit starts at |1>, rotates pi/2 around the x axis, and then rotates another pi/2 around the x axis; two pi/2 rotations equals one pi rotation, which is the equivalent of applying the Pauli-X gate — the NOT gate — which means that the initial |1> state essentially has a NOT gate applied to it, flipping it to |0> and showing it as “off.”
The middle qubit, by the way, is the reason why you can solve this puzzle with a Fredkin gate and a CNOT without having any intuition as to why they are needed. Normally, you would expect these gates to actually do something, but while you are scratching your head trying to figure out how they are affecting the final probabilities, you are not suspecting that they are essentially doing nothing. In reverse engineering the black box, I discovered that I needed to effectively cancel out both multi-qubit gates in the solution, which means that solving the puzzle essentially involvd stumbling upon cancelling out the multi-qubit gates in the black box.
IBM Q circuit
I recreated the full circuit — black box included — in IBM Q. The IBM Q circuit diagram better showcases the distinct segments of the circuit, from left to right:
- the initial states
- the black box
- the solution
- measurements, since there are no off/on indicators available
IBM Q simulated result
The IBM Q simulator confirms that the full circuit results in all three qubits measuring 0 with a probability of 1, which would show as “off” in Quirk. I wasn’t really doubting Quirk; this was more a matter of confirming that I transferred the circuit over completely and correctly.
transpiled circuit, simulator
This is how the circuit transpiles for the simulator. The most noteworthy changes are that the Fredkin gates (controlled-SWAP gates) each transpile into one Toffoli gate and two CNOT gates.
And, this is the result on ibmqx2, a real 5-qubit quantum processor. It’s nice to see that the correct result has the highest probability of being measured, especially considering the depth of the circuit; I would not have been surprised to see a uniform distribution (all outcomes having equal probabilities). For any readers who may be new to quantum computing, just know that quantum processors are still very much in their infancy and are very prone to errors, which is why the qubits may show as “on” even though everything was done correctly to turn them “off.”
transpiled circuit, ibmqx2
And, finally, here is how IBM Q breaks the circuit down in order to run it on ibmqx2. This is just provided as an appendix, in a way; I’m not going to walk through it. However, if this was a circuit worth optimizing, it’s often valuable to analyze transpiled circuits for ways to manually optimize them. In this particular case, perhaps there is some other way to solve the puzzle and some other way to deconstruct the black box. However, I’m satisfied with having solved the puzzle at least one way and fully understanding how this particular circuit works, so I’ll just wait for the next challenge.
Since drafting this article and preparing it for publication, I have learned that there are several ways to solve this puzzle, and at least one other way to build the black box. Whereas the creator of the puzzle approached it from something that he has worked quite a bit on, I approached it from something very different that I’ve been working on. Therefore, my solution was unanticipated. And, since I wouldn’t have guessed his actual black box, I ended up discovering an alternate way to do what he did.
Consequently, we are both eager to analyze our different circuits. How did my solution solve his black box? When he was exploring his approach, I remember him tweeting about SWAPs, so the Fredkin gate in my solution is of particular interest. Also, how do our black boxes arrive at the same states? At the time of this writing, we’ve learned that my black box uses fewer pre-transpiled gate operations than the actual black box; can we use this to shorten a popular algorithm?
We thought that solving the puzzle would be the fun part, but the aftermath is shaping up to be even more interesting!