QC — Programming with Quantum Gates (2-Qubit operator)

Image for post
Image for post
Photo by Vincent van Zalinge

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.

Image for post
Image for post

i.e.

Image for post
Image for post

It is troublesome to lay out all the possibilities. So it is often represented as:

Image for post
Image for post

which implements

Image for post
Image for post

⊕ 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:

Image for post
Image for post

The following is its shorter notation:

Image for post
Image for post

The matrix form for CNOT-gate is:

Image for post
Image for post

This may take a while to soak in the notation but it is important.

Image for post
Image for post

Here is another example using an ancillary qubit |1⟩ for control. Check out how it impacts a superposition of the target bit.

Image for post
Image for post

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.

Image for post
Image for post

i.e.

Image for post
Image for post

This is the output with control qubits |0⟩ or |1⟩.

Image for post
Image for post

Here is a controlled-Z gate

Image for post
Image for post

and the corresponding operator in the matrix form.

Image for post
Image for post

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.

Image for post
Image for post

Quantum parallelism

Quantum parallelism applies a function to a superposition |x⟩ like:

Image for post
Image for post

For example, we prepare a superposition x containing both |0⟩ and |1⟩ basis.

Image for post
Image for post

Here is the output for the qubits.

Image for post
Image for post

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

Image for post
Image for post

Then we can apply controlled-U gates to prepare (say):

Image for post
Image for post

The diagram below is an example of applying controlled-U gates to prepare a superposition which is used to approximate the superposition above.

Image for post
Image for post
Image for post

Controlled-U implementation

The operator U can be rewritten as

Image for post
Image for post

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):

Image for post
Image for post

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.

Image for post
Image for post
Image for post
Image for post

If we apply the gate twice in a row, it restores the original input. i.e. it is reversible. Indeed, it is unitary.

Image for post
Image for post

Again, this can be implemented by combining single and 2-qubit gates:

Image for post
Image for post

Here is its the exact implementation.

Image for post
Image for post
Modified from source

The matrix form is:

Image for post
Image for post

And the corresponding output.

Image for post
Image for post
Modified from source

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).

Image for post
Image for post

We want to create a circuit

Image for post
Image for post

At a high level, we prepare the superposition position for n-qubits and have the (n+1)th qubit as the target:

Image for post
Image for post

Here is the controlled-SAT that implements our 3-SAT example.

Image for post
Image for post
Modified from source

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.

Image for post
Image for post
Modified from source

Here is the whole circuit that implements the Grover algorithm.

Image for post
Image for post
Source

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.

Image for post
Image for post

So it is simplified to:

Image for post
Image for post

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.

Image for post
Image for post
Source

For the entanglement above, we apply the Hadamard gate before the controlled-not gate.

Image for post
Image for post

Here are the different ways to create different Bell states:

Image for post
Image for post

Other examples

Here are some more examples.

Controlled-U with multiple control bits:

Image for post
Image for post

Multiple control and target bits:

Image for post
Image for post

Reverse the control bits:

Image for post
Image for post

Multiple targets for CNOT-gate.

Image for post
Image for post

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:

Image for post
Image for post
Source

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.

Image for post
Image for post

But it is actually not possible for an arbitrary state when we don’t know the state:

Image for post
Image for post

Here, we are expecting

Image for post
Image for post

But in fact, we get

Image for post
Image for post

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.

Written by

Deep Learning

Get the Medium app