Entanglement in Quantum Computing

In quantum computing, the interplay of quantum superposition and entanglement gives rise to a diverse spectrum of algorithms that have no classical analogs. At one end, we have algorithms that go straight to the heart of entanglement to encrypt tamper-proof messages. (We’ll review this method in Chapter 9, ​Alice in Quantumland—Quantum Cryptography​.) On the other end, in quantum search, where our chief concern is canceling qubelet combinations in the mega-qubit, entanglement couples quantum states, causing them to gyrate in unintended ways, rendering the superposition-of-all-states-at-once ineffective. So, in the next section, we investigate how to modify our quantum programs to unravel these states.

Basic Idea

We’ve seen that all it takes to entangle qubits is a couple of gates, for example, the H and CNOT gates. And, as these gates are regularly used in quantum circuits, entangled qubits are more the rule than the exception in our programs.

Once qubits are locked into entangled states, it’s impossible to then transform them to other states that cancel out. Simply put, entangled qubits interfere with the controlled cancellation of quantum states. Specifically, in the Hotel Scheduling Problem introduced in ​A Scheduling Problem​, the gates representing the schedule constraints entangle the qubits representing the performers with the working qubits, which are the targets of the CNOT gates. So, we snap qubits out of their entangled states by setting them back to their original states. We can then continue to operate on the disentangled qubits and remove unwanted states that don’t meet the constraints.

Qubits can be restored back to their original states by recognizing the following operations:

• Back-to-back H gates
• Back-to-back CCNOT gates

We reviewed the first case in ​Back-to-Back H Gates: The First Hint of Taming Randomness​. For the second case, consider the following circuit:

In particular, let’s see whether the two back-to-back CCNOT gates restore qubits to their original quantum states after they act on them. That is, we want to investigate whether the quantum state after the H gate acts on the q[0] qubit, which together with q[1] and q[2] we’ll call the left quantum state, is recovered after the CCNOT gates acts on them.

This left quantum state is the mega-qubit formed by the qubelets of the q[0] qubit after it’s split by the H gate and combined with the qubelets of the qubits in q[1] and q[2]. To strengthen our dexterity with analyzing quantum circuits, we’ll construct this mega-qubit mentally: the qubit in q[0] consists of a pentagon qubelet that’s split by the H gate into a pentagon qubelet and a triangle qubelet. Next, each of these qubelets links up with the triangle qubelets associated with the qubits in q[1] and q[2], respectively. Thus, we end up with a mega-qubit consisting of two qubelet columns or combinations, as shown in the left mega-qubit in the figure:

Recall from ​Controlled Controlled NOT (CCNOT) Gate​, that only when both control bits are , the CCNOT gate inverts the target qubit. In the first qubelet combination, the top cell is a pentagon qubelet. So this qubelet combination isn’t affected by the CCNOT gate and remains as is as shown in the first column in the center mega-qubit. The second qubelet combination on the left, though, has a triangle qubelet on both its control bits. Thus, the first CCNOT gate switches the triangle qubit in the bottom cell, associated with the q[2] qubit, its target. This operation is shown in the second column of qubelets in the center mega-qubit. The center mega-qubit, then, is the quantum state after the first CCNOT gates on the qubits.

In a similar way, the second CCNOT gate acts on the two qubelet combinations in the center mega-qubit, resulting in the qubelet combinations in the right mega-qubit. This right mega-qubit has identical qubelet columns to the one on the left. That is, the quantum state on the left mega-qubit is the same as that on the right, indicating that back-to-back CCNOT gates recover the original left quantum state.

Thus, both back-to-back H gates and back-to-back CCNOT gates are their own inverses. Wherever we see these gates acting on qubits, we can reset those qubits by immediately using those gates again on those qubits.

Disentangling Qubits

To get a feel for disentangling qubits, consider the following circuit:

In this circuit, q[0] is and the others, q[1]--q[3] are each . This will be the original quantum state that we’ll recover.

Although we can use the qubelets model to study how this circuit modifies the qubits, this time we’ll directly run the quantum program listed here:

On line 6, we declare a NOT gate to initialize the q[0] qubit to . The Measure gates are declared on lines 17--20. On line 15 we declare a CZ gate. This CZ gate is the IBM Quantum Computer’s built-in gate and is realized identically to what we studied in ​Realizing a Controlled Z Gate​.

If you run this program, you’ll get an output similar to the output shown.

This program ran on a 5-qubit real quantum computer using 8192 shots.

The classical register shows multiple states, indicating that the qubits collapse to several states. In other words, the gates have put the qubits in a mega-qubit holding many qubelet combinations—that is, in a superposition of quantum states.

If we simply disentangle the qubits by reversing the action of all gates, including the CZ gate acting on the q[3] qubit, we’ll just get back to where we started and won’t have made any headway toward finding an optimal solution.

Recognizing that the CZ gate is used to tag optimal states in the mega-qubit while non-optimal states are left alone, as described in ​Using the Controlled Z Gate in Practice​, we won’t undo its operation. We’ll only reverse the action of the gates to the left of the CZ gate. As a result, qubelet combinations that are not optimal get disentagled so that subsequent gates can remove them.

Disentanging Qubits Implies Disentagling Qubelets
	When you disentangle qubits, you should think in terms of disentangling qubelets in the various qubelet combinations or columns in the mega-qubit.

To overturn the operations of the gates to the left of the CZ gate, hook up gates to the right of the CZ gate so that these new gates mirror those on the left, as shown within the box with the solid border in the figure:

The code listing for disentangling the qubits is shown.

The “mirror image” gates are flagged; you declare them in the reverse order of those before the CZ gate.

When you run this circuit, you’ll see that the original state is recovered, as shown in the following output:

This program ran on a 5-qubit real quantum computer using 8192 shots.

The binary state that’s most often seen is 0001. Recall that the classical states are labeled as a concatenated string with c[4] on the left and c[0] on the right. Thus, 0001 corresponds to the classical state with c[0] holding 1 and c[1]--c[3] equal to 0. This classical state is obtained when the q[0] qubit collapses to and the q[1]--q[3] qubits each to . So, in quantum computing, because we can never directly examine the quantum state of a qubit, all we can ever say is that we have recovered the original quantum state, perhaps with a different orientation.

Disentangling the Bellagio Constraints

In a quantum program, not all qubits have to be disentangled. So that you know which qubits are slated for disentangling, consider again the quantum circuit for the Bellagio Constraints but this time with the H and CZ gates hooked up as described in ​Using the Controlled Z Gate in Practice​:

The mega-qubit after the Controlled Z gate on the right is shown in the figure.

The bottom cell of each column in the mega-qubit shows the qubelet in the q[7] qubit after the Controlled Z gate. The second and third columns have inverted triangle qubelets, indicating that the qubelets in the corresponding columns give a solution that satisfies the Boolean expression—they are a valid schedule. The first and fourth columns give bookings that violate the constraints. You’ll learn to get rid of these columns in the mega-qubit in Chapter 10, ​Quantum Search​.

First, though, before applying those techniques, the qubits need to be disentangled, otherwise they’ll forever be stubbornly locked in their current states and you won’t be able to cancel them out. If you disentangle all the qubits, you’re back where you started. Since you want solutions corresponding to a valid schedule, you want to keep the columns that are tagged as workable. That is, you want to retain the qubelets in the bottom cell of each column in the mega-qubit. In other words, you only need to disentangle the qubits in q[0]--q[6].

To disentangle the qubits in q[0]--q[6], you reverse the operations of the logic gates so that they form a mirror image around an imaginary vertical line passing through the Controlled Z gate, as shown here:

Notice that only a small part of this circuit relies on quantum effects—the H gates on the left and the Controlled Z gate on the right. The rest of the circuit deals with the standard logic operations, albeit for quantum hardware.

You’ll also see that several qubits are acted on by back-to-back X gates. These effectively don’t affect the quantum state and can be removed. We’ll leave them in the circuit, however, so that you see the pattern. Later, after you’ve verified the program works, you can remove these redundant gates.

We’ll leave this circuit here and turn our attention to look at ways that precisely guide qubits from one quantum state to another. We’ll pick up the tale again in Chapter 10, ​Quantum Search​, where we’ll apply these techniques to eliminate the unwanted columns in the mega-qubit.

Using Entanglement in Applications

Entanglement is a “pure” quantum phenomenon that you’ll never encounter in classical computing. Before you can fully leverage this effect, you need to learn a few more concepts in Chapter 6, ​Designer Genes—Custom Quantum States​, and Chapter 7, ​Small Step for Man—Single Qubit Programs​. With this background, you’ll see how it’s used in real-world applications in Chapter 9, ​Alice in Quantumland—Quantum Cryptography​.