Magic state distillation and gate teleportation

In fault tolerant quantum computing, Clifford gates have many desirable properties in stabilizer codes. For example, they can be implemented transversally and their noise is contained locally [1]. Therefore, there is a strong preference to include Clifford gates in a logical gateset. However, Clifford gates alone do not form a universal gateset. At least one non-Clifford gate is needed to perform universal quantum computing. Magic states are certain quantum states that enable universal fault-tolerant quantum computing with Clifford gates and preserve the desirable properties of the Clifford gates. With magic states, we can effectively apply non-Clifford gates using only Clifford gates, forming a universal gateset.

In this notebook, we first demonstrate how to implement a non-Clifford gate with only Clifford gates and magic states. This procedure is known as “gate teleportation”. Because the preparation of the magic state in this first demonstration is not fault-tolerant (i.e., it is not prepared with an error correction code), it is subject to noise.

In the second demonstration, we introduce a procedure to create logical magic states based on the 5-qubit error correction code [2], called magic state distillation [1]. This procedure is based on post-selection, so the preparation of magic states has a finite probability of failing under this protocol.

Finally, we introduce a “repeat until success” protocol [3] that guarantees every execution prepares a magic state successfully. For all the protocols in this notebook, we use AutoQASM to program these procedures, demonstrating AutoQASM’s ability to express the classical control flow needed for magic state distillation and how AutoQASM enables early fault-tolerant quantum computing experiments.

Let’s first import the modules used in this notebook.

# general imports
from collections import Counter, defaultdict
from typing import Dict, List

import numpy as np

# AutoQASM imports
import autoqasm as aq
import autoqasm.instructions as ins

# AWS imports: Import Braket SDK modules
from braket.devices import LocalSimulator

Apply non-Clifford gates with magic states

To form a universal gateset, at least one non-Clifford gate is needed in addition to Clifford gates. This additional gate is commonly chosen to be \(RZ(\pi/4)\) or \(RZ(\pi/6)\) gate. These non-Clifford gates are not possible to implement transversally with stabilizer code. Including these non-Clifford gates would lose the desirable properties of Clifford gates. Here is where magic states come to the rescue. In this section, let’s learn how to apply a \(RZ(\pi/6)\) gate with only Clifford gates and a magic state [1], a procedure known as gate teleportation. Similar to state teleportation, gate teleportation uses forward feedback to form dynamic circuits, but with the intention of applying a quantum gate instead of teleporting a quantum state. For simplicity, we first focus on demonstrating the algorithm of gate teleportation with a physical circuit, i.e., without encoding to an error correction code. The same algorithm can also apply to logical circuits, by replacing the Clifford gates and the magic state with the logical version. After this section, we will introduce how to create a logical magic state.

First, we define a subroutine, physical_magic_state_a_type, to create a A-type physical magic state, \(\ket{A_{\pi/6}} = \frac{1}{\sqrt{2}}(\ket{0}+e^{i\pi/6}\ket{1})\) [1]. Because the example will be executed on an ideal simulator, the subroutine creates an ideal magic state. But on a near-term hardware, this magic state preparation would be subject to noise.

For demonstration purposes, we define a subroutine, basis_rotation_pi6, that rotates the basis of a quantum state before a measurement. This helps verify that the main program introduced later indeed implements a \(RZ(\pi/6)\) gate on the data qubit. This subroutine is not a key part of gate teleportation.

@aq.subroutine
def physical_magic_state_a_type(q: int):
    ins.h(q)
    ins.rz(q, np.pi / 6)


@aq.subroutine
def basis_rotation_pi6(q: int):
    ins.rz(q, -np.pi / 6)
    ins.h(q)

The main program gate_teleportation below demonstrates applying a \(RZ(\pi/6)\) gate on a data qubit. The data qubit can start out in any state. Without loss of generality, we prepare the data qubit in \(\ket{\text{data}} = \frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\). We also prepare a magic state on an ancilla qubit. Then, we apply a CNOT gate over the data and ancilla qubit. Up to this point, the 2-qubit quantum state is

\[(\ket{0}+e^{i\pi/6}\ket{1})\ket{0} + (e^{i\pi/6}\ket{0}+\ket{1})\ket{1} .\]

By measuring the ancilla qubit (the second qubit) and post-selecting the results with measurement outcome = 0, the procedure effectively implements a \(RZ(\pi/6)\) gate on the data qubit. To verify the resulting data qubit state is in the target state \(RZ(\pi/6)\ket{\text{data}} = \frac{1}{\sqrt{2}}(\ket{0}+e^{i\pi/6}\ket{1})\), we rotate the state in the data qubit and then measure it.

@aq.main(num_qubits=2)
def gate_teleportation():
    q_data = 0
    q_magic = 1

    # state preparation
    ins.h(q_data)
    physical_magic_state_a_type(q_magic)

    # apply CNOT
    ins.cnot(q_data, q_magic)

    # measure data qubit in the target basis, measure ancilla in z-basis
    basis_rotation_pi6(q_data)
    return ins.measure([q_data, q_magic])

Here is a helper function to compute marginal probability. It is used in the analysis following this code block.

def get_marginal_probs(probs: Dict[str, float], targets: List[int]) -> Dict[str, float]:
    """Get marginal probabilities of a distribution.

    Args:
        probs (Dict[str, float]): Original probability distribution.
        targets (List[int]): The qubits to compute marginal probability.

    Returns:
        Dict[str, float]: Marginal probabilities.
    """
    new_probs = defaultdict(float)
    for bitstring, value in probs.items():
        new_bitstring = "".join([bitstring[t] for t in targets])
        new_probs[new_bitstring] += value

    total_shots = sum(new_probs.values())
    return {k: v / total_shots for k, v in new_probs.items()}

Now, we are ready to run the gate teleportation program on a local simulator. The measurement counts are then post-selected to keep those which measure “0” on the ancilla qubit. The Z expectation value of the data qubit is 1.0, confirming that we indeed implemented \(RZ(\pi/6)\ket{\text{data}}\).

# Get measurement result
result = LocalSimulator("autoqasm").run(gate_teleportation, shots=100).result()
counts = Counter(result.measurements["return_value"])
print("measurement counts: ", counts)

# Post-select the measurement outcome that measures "0" in ancilla
post_selected_counts = {k: v for k, v in counts.items() if k[1] == "0"}

# Compute the expectation value of Z observable on the data qubit
marginal_probs = get_marginal_probs(post_selected_counts, [0])
expval = marginal_probs.get("0", 0) - marginal_probs.get("1", 0)
print("Z expectation value: ", expval)

measurement counts:  Counter({'00': 52, '01': 42, '11': 6})
Z expectation value:  1.0

Magic state distillation

We have seen how injecting a magic state into the quantum program enables the \(RZ(\pi/6)\) gate, which, when combined with the Clifford gates, forms a universal gateset. In the above demonstration, the magic state is prepared as a physical state. It is subject to noise on a near-term device. In this section, we demonstrate how to create a logical T-type magic state, \(\ket{T}=\cos{\beta}\ket{0}+e^{i\pi /4}\sin{\beta}\ket{1}\) with \(\beta=\frac12 \arccos{\frac{1}{\sqrt{3}}}\), based on the 5-qubit error correction code [1, 2]. The T-type magic state is closely related to the A-type, \(\ket{A_{\pi/6}}\), introduced in the previous section. The logical A-type magic state can be obtained by post-selecting the +1 outcome of \(Z\otimes Z\) stabilizer on a \(\ket{T}\otimes\ket{T}\) state and discarding the second qubit, a procedure detailed in Ref[1].

We first define a subroutine, physical_magic_state_t_type, to create a T-type physical magic state. On a near-term hardware, this magic state preparation would be subject to noise.

@aq.subroutine
def physical_magic_state_t_type(q: int):
    ins.ry(q, np.arccos(1 / np.sqrt(3)))
    ins.rz(q, np.pi / 4)

Then, we define a subroutine for the decoder of the 5-qubit error correction code. Measurements after running the decoder are typically used as error syndromes which inform the types of errors in the quantum state. Here, however, we will use the measurement results to post-select desired states.

@aq.subroutine
def decoder(q0: int, q1: int, q2: int, q3: int, q4: int):
    ins.cnot(q1, q0)
    ins.cz(q1, q0)
    ins.cz(q1, q2)
    ins.cz(q1, q4)

    ins.cnot(q2, q0)
    ins.cz(q2, q3)
    ins.cz(q2, q4)

    ins.cnot(q3, q0)

    ins.cnot(q4, q0)
    ins.cz(q4, q0)

    ins.z(q0)
    ins.z(q1)
    ins.z(q4)

    ins.h(q1)
    ins.h(q2)
    ins.h(q3)
    ins.h(q4)

The code snippet below is the main program for magic state distillation. First, we prepare a physical magic state on each of the five qubits. The qubit 0 is the data qubit, while the other four are ancilla. Then, the decoder subroutine is applied on all qubits. Finally, a rotation layer, consisting of a H gate and a Y gate, is needed to rotate the state in data qubit to the magic state. The magic state is successfully “distilled” only when all ancilla are measured as “0” [1].

@aq.main(num_qubits=5)
def distillation():
    # state preparation
    for q in aq.qubits:
        physical_magic_state_t_type(q)

    # decoding
    decoder(*aq.qubits)

    # final rotation
    ins.h(0)
    ins.y(0)

    # measure ancilla
    c = ins.measure([1, 2, 3, 4])  # noqa: F841

We run the distillation program on a local simulator.

n_shots = 1000
result = LocalSimulator("autoqasm").run(distillation, shots=n_shots).result()
counts = Counter(result.measurements["c"])
print("measurement counts: ", counts)

measurement counts:  Counter({'0000': 150, '0110': 69, '0001': 65, '0100': 61, '1011': 61, '1101': 60, '0011': 58, '1100': 57, '0101': 56, '1110': 54, '1000': 53, '1010': 53, '1111': 52, '1001': 52, '0111': 50, '0010': 49})

About 1/6 of the total shots correspond to successful preparations of T-type magic state on qubit 0 (i.e., measuring “0000” in ancilla), agreeing with the result in Ref[1].

success_count = len([x for x in result.measurements["c"] if x == "0000"])
print("success ratio: ", success_count / n_shots)

success ratio:  0.15

Repeat until success

To guarantee a successful preparation of the magic state in every shot, we introduce a repeat-until-success (RUS) protocol [3].

For demonstration purposes, we first define a subroutine, basis_rotation_t_type, that rotates the basis of a quantum state before a measurement. This helps verify that the main program introduced later indeed create a T-type magic state on the data qubit. This subroutine is not a key part of magic state distillation and the RUS protocol.

@aq.subroutine
def basis_rotation_t_type(q: int):
    ins.rz(q, -np.pi / 4)
    ins.ry(q, -np.arccos(1 / np.sqrt(3)))

In the main program, distillation_rus, the state preparation and the decoding are repeated until all ancilla measure “0”. This RUS protocol guarantees that every shot ends up with successful magic state preparation. This protocol requires while-loops in the quantum program because we continue to retry until the success condition is met. It guarantees that every shot ends up with successful magic state preparation, distilling the magic state.

@aq.main(num_qubits=5)
def distillation_rus():
    # RUS: repeat until measuring all-zero in ancilla
    c1 = aq.BoolVar(True)
    while c1:
        # state preparation
        for q in aq.qubits:
            ins.reset(q)
            physical_magic_state_t_type(q)

        # decoding
        decoder(*aq.qubits)

        # measure ancilla
        c = ins.measure([1, 2, 3, 4])
        c1 = c[0] or c[1] or c[2] or c[3]

    # final rotation
    ins.h(0)
    ins.y(0)

    # measuring in the basis of magic state
    basis_rotation_t_type(0)
    c2 = ins.measure(0)  # noqa: F841

Running the RUS version of magic state distillation, the expectation value on the data qubit (qubit 0) is 1.0, indicating that T-type magic states are successfully prepared in all 20 shots.

result = LocalSimulator("autoqasm").run(distillation_rus, shots=20).result()
counts = Counter(result.measurements["c2"])
probs = {str(k): v / sum(counts.values()) for k, v in counts.items()}

expval = probs.get("0", 0) - probs.get("1", 0)
print("Z expectation value: ", expval)

Z expectation value:  1.0

Summary

In this notebook, we demonstrate and execute the protocol of magic state distillation and gate teleportation. These protocols are at the core of fault tolerant quantum computing with stabilizer codes. The procedure not only requires feed forward control flow, but also the expressibility of while-loop. We show that AutoQASM has the ability to express quantum programs that tie these complex classical control flow to quantum instructions.

Reference

[1] S. Bravyi et al., Universal Quantum Computation with ideal Clifford gates and noisy ancillas. arXiv: https://arxiv.org/abs/quant-ph/0403025

[2] C. H. Bennett et al., Mixed State Entanglement and Quantum Error Correction. arXiv: https://arxiv.org/abs/quant-ph/9604024

[3] A. Paetznick et al., Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries. arXiv: https://arxiv.org/abs/1311.1074