QC — Programming with Quantum Gates (2-Qubit operator)
Quantum computers are built on top of single-qubit and 2-qubit operators. In the last part, we cover the single-qubit. Here, we will finish the 2-qubit operators and see how other multiple-qubit operators are built on top of them with some examples. The 2-qubit operators are harder to understand. But it is important. Technically, it creates entanglement. It can be proven that no quantum supremacy can be done without entanglement.
CNOT-gate (controlled-NOT)
CNOT-gate operates on two qubits: the control qubit |x⟩ and the target qubit |y⟩. If the control qubit is 0, it does nothing to the target qubit. Otherwise, it flips it. This is one of the most common gates in a quantum algorithm.
i.e.
It is troublesome to lay out all the possibilities. So it is often represented as:
which implements
⊕ is the addition modulo 2 operation (a.k.a. “exclusive or”). |x⟩ can be in a superposition composed of many computational bases. One example of such basis in a 3-qubit system is:
The following is its shorter notation:
The matrix form for CNOT-gate is:
This may take a while to soak in the notation but it is important.
Here is another example using an ancillary qubit |1⟩ for control. Check out how it impacts a superposition of the target bit.
Controlled-U gate
The concept of CNOT-gate can be generalized to any unitary operations. Similar to CNOT-gate, Controlled-U gate has a control and a target bit. U is a unitary operator implemented by a quantum circuit. When the control bit is |1⟩, it applies U to the target bit, otherwise, no change to the target bit.
i.e.
This is the output with control qubits |0⟩ or |1⟩.
Here is a controlled-Z gate
and the corresponding operator in the matrix form.
The diagram below is one of the most common design patterns where we use an ancilla qubit |0⟩ for the target to prepare f(x). This demonstrates the capability of quantum parallelism of applying a function to all bases of the superposition.
Quantum parallelism
Quantum parallelism applies a function to a superposition |x⟩ like:
For example, we prepare a superposition x containing both |0⟩ and |1⟩ basis.
Here is the output for the qubits.
This is called quantum parallelism because we compute f(x) for all computational bases all in parallel.
As another example, we apply Hadamard gates to prepare x as
Then we can apply controlled-U gates to prepare (say):
The diagram below is an example of applying controlled-U gates to prepare a superposition which is used to approximate the superposition above.
Controlled-U implementation
The operator U can be rewritten as
A, B, and C are single-qubit operations and ABC = I. Therefore, the Controlled-U gates can be broken down as (section 4.3 in here for more details):
A similar concept in the next section will build a multiple-control CNOT-gate using 2-qubit operators. But what is important, we can introduce a phase exp(iα) in the control bit which is important when we study the phase estimation & Shor’s algorithm in a later article.
TOFFOLI gate
TOFFOLI gate can be used to simulate standard boolean operations. It negates a target bit if both control qubits are 1.
If we apply the gate twice in a row, it restores the original input. i.e. it is reversible. Indeed, it is unitary.
Again, this can be implemented by combining single and 2-qubit gates:
Here is its the exact implementation.
The matrix form is:
And the corresponding output.
Examples
Controlled SAT gate
Let’s get some more examples of the controlled-U gate. Let’s consider a 3-SAT problem (Boolean satisfiability problem). It is a boolean function with clauses composed of at most three variables. We want to know whether there are some values of these variables that evaluate the function to be true (satisfiable). This problem is very hard to solve as the number of variables increases (say 50 variables).
We want to create a circuit
At a high level, we prepare the superposition position for n-qubits and have the (n+1)th qubit as the target:
Here is the controlled-SAT that implements our 3-SAT example.
We introduce 4 work bits and 1 target bit into the bottom of the circuit. The 4 work bits are temporary storage in preparing the target bits. To reuse the resource, we often apply the reverse of the logic to restore those bit to the original state.
Here is the whole circuit that implements the Grover algorithm.
Because the ancilla bit does not change after we reverse its operation, we often do not include them in describing the superposition even they are needed in the actual circuit.
So it is simplified to:
The information of the ancilla bits between the calculation is often called “garbage”.
Entanglement
Next, let’s show how entanglement can be created with controlled-not gate.
For the entanglement above, we apply the Hadamard gate before the controlled-not gate.
Here are the different ways to create different Bell states:
Other examples
Here are some more examples.
Controlled-U with multiple control bits:
Multiple control and target bits:
Reverse the control bits:
Multiple targets for CNOT-gate.
As shown, the corresponding physical gate design can be quite complex. The scope of this series is to demonstrate quantum computing. So we will not detail the low-level gates design further.
Recap
Here is the summary of most common gates:
No cloning theorem
The no-cloning theorem indicates that it is impossible to create a precise copy of an arbitrary unknown quantum state. It sounds like it is false from the circuit below which |1⟩ is successfully copied to the target qubit.
But it is actually not possible for an arbitrary state when we don’t know the state:
Here, we are expecting
But in fact, we get
So if the states are known, we can duplicate it, but not for an arbitrary state. In short, nature does not allow us to clone an arbitrary superposition precisely. This is an important feature for quantum cryptography since you cannot make a secret copy of a qubit. The only way to read a qubit is to measure it which will collapse the superposition and detectable by some statistic analysis, i.e. no eavesdropping.
Next
Before writing the first quantum program, we can look at some implementation issues that are unique to quantum computing first.
Otherwise, we can jump into our first quantum algorithm and program.
