Designing a Software Stack for Quantum Programs with Error Correction

Quantum processors differ fundamentally from classical computers. They leverage particles governed by quantum mechanics to perform computations using principles like superposition, entanglement, and interference. These properties allow quantum processors to perform certain tasks far more efficiently than classical computers. However, this efficiency comes at a cost: quantum computations are prone to extremely high error rates, which make long-running computations infeasible.

Error correction techniques, analogous to those used in long-distance communication, can mitigate this problem. The objective is to enable long-running quantum calculations by transparently integrating an error correction layer that reduces the error rate sufficiently to avoid computational failures. It is not that errors are completely removed, just mitigated enough to be able to confirm the result.

Key Challenges:

1. Classical Computation in Error Correction: Error correction inherently involves classical computation as it requires real-time measurements and corrections based on classical logic. Designing a software stack that transparently enables quantum error correction layer without introducing a fully hybrid language is a significant challenge. The stack must bridge the gap between quantum and classical processing seamlessly.

2. Hardware and Code Dependence: Quantum processors typically offer a small, hardware-specific set of universal instructions from which all other operations can be derived. These instruction sets vary across hardware platforms, reflecting differences in the underlying quantum technologies. Similarly, quantum error correction codes define their own universal sets of instructions, which differ between codes. This diversity complicates the development of a universal software stack.

The qstack approach:

With qstack, we propose a generic mechanism to define a layer of quantum compilation and evaluation. qstack introduces clear and simple boundaries between classical and quantum computation to support two key types of composition:

• Horizontal Composition: Enables the composition of quantum instructions, even when implemented using fault-tolerant circuits with real-time error correction. Each quantum instruction consists of a computation graph generated by one or more layers from encoding and decoding quantum instructions.

• Vertical Composition: Allows layering to build concatenated error correction codes and decompositions to connect different layers.

qstack is designed to be platform-agnostic and qec code-agnostic, providing flexibility to adapt to diverse hardware platforms and error correction strategies. This design ensures the stack can support scalable quantum computations while remaining transparent to the user.

Ideas

• Pure quantum language with support for classical integration.
• Clear and simple boundaries between classical and quantum execution.
• Dynamic layers define both classical and quantum instructions.
• Clear seperation of concerns and responsibilities between cpu and qpu

Programs and Kernels

A quantum program is comprised of a list of kernels. A kernel represents a unit of quantum computation consisting of:

program             :== kernels
kernels             :== kernel
                      | kernel kernels
kernel              :== target: instructions
instructions        :== instruction instructions | *None*
instruction         :== quantum_instruction
                      | kernel
quantum_instruction :== op targets
op                  :== *id*
target              :== qubit_id | *None*

A kernel allocates the target qubit id and initializes it in the |0⟩ state, applies some quantum instructions, and measures it.

The simplest kernel that always returns the value 0 would be:

allocate q1:
measure

Notice we use the allocate and measure syntax to represent the boundaries of a kernel.

A kernel with a flip instruction would always return 1:

allocate q1:
  flip q1
measure

Kernel Semantics

Kernels follow typical quantum programs semantics.

A kernel's allocate initializes a single qubit, represented with a quantum state. This state is a 2-dimensional vector indicating the complex amplitude probabilities for measuring 0 or 1. The qubit is always initialized in the state [1, 0] also represented as ket |0⟩, corresponding to a 100% probability of measuring 0.

Instructions inside a kernel modify the state by applying a unitary matrix. These operations transform the quantum state while preserving the total probability.

A kernel measure deallocates the associated qubit and returns either 0 or 1, based on the respective probabilities defined by the state amplitudes.

A kernel can embed other kernels. Each time a qubit is allocated, the state size doubles, representing the probability of measuring the tensor product of the existing space with 0 and 1. Other qubits remains in scope, allowing operations to be applied across all allocated qubits.

allocate q1:
  allocate q2:
  measure
measure

Instructions are applied to the entire state. If an instruction specifies a single qubit, it is understood as the Kronecker product of the one-qubit operation with the Identity operator applied to the remaining qubits. This ensures the operation affects only the specified qubit while leaving the rest of the computational state unchanged.

At the end of the kernel the qubit is measured; which collapses the state of the entire system. The state is projected onto one of two subspaces corresponding to the outcome (0 or 1) of the last computational space added to the system. The outcome depends on the state, with probabilities determined by the amplitudes of the basis states. The resulting state is renormalized to ensure the total probability remains 1, modifying the amplitudes of all basis states in the system accordingly.

Measurements are typically collected at runtime and stored in a FILO stack. The outcome of the program are the remaining measurements in the stack.

A simple program that prepares and measures a bell-state could be represented as:

allocate q1:
  allocate q2:
    mix q1
    entangle q1 q2
  measure
measure

It is a common pattern to initialize and measure together multiple qubits, so we provide syntactic sugar for this. This is an equivalent bell-state preparation:

allocate q1 q2:
  mix q1
  entangle q1 q2
measure

In certain scenarios it is necessary to define kernels that do not need to allocate and measure a new target. This can be useful, for example, to indicate time-steps:

allocate q1 q2:
  mix q1
  alocate:
    entangle q1 q2
  measure
measure

We use --- in the syntax to indicate such kernels:

allocate q1 q2:
  mix q1
  ---
  entangle q1 q2
measure

Hybrid kernels

A kernel can incorporate classical computation after its measurement. For this, we enhance qstack's grammar as follows:

kernel                  :== target: instructions classical_instruction
classical_instruction   :== *None*
                          | op

We indicate the invocation of a classical instruction in the program using >>.

Take for example the following program implementing the Teleport protocol:

allocate target:
  allocate shared source:
    # prepare source in some random state
    ---
    >> prepare(q=source)

    # entangle shared and target
    h shared
    cx shared target

    # deentangle source and shared
    cx source shared
    h source
  measure
  >> fix(q=target)
measure

prepare and fix are classical functions. A classical function returns a new kernel for evaluation. In this case, prepare returns a kernel that rotates the qubit by a random angle, and fix applies the correction needed for the state to be correctly teleported to the target qubit. They both takes a single parameter, q, indicating the qubit to apply the operation to:

op = random.choice([X, H])

def prepare(*, q: QubitId):
    return Kernel(targets=[], instructions=[op(q)])

def fix(m0: Outcome, m1: Outcome, *, q: QubitId):
    instructions = []
    if m1 == 1:
        instructions.append(Z(q))
    if m0 == 1:
        instructions.append(X(q))
    return Kernel(targets=[], instructions=instructions)

fix also takes two measurement outcomes. Notice these do not need to be specified in the program. These outcomes will automatically be consumed from the measurement stack.

Decoders

A decoder is a classical method that, given a list of measurement outcomes, returns a new outcome.

Take for example a simple majority bit vote encoding:

def vote(m1, m2, m2):
    if sum([m1, m2, m3]) > 2
        return 1
    else:
        return 0

As with other classical instructions, it consumes measurements from the stack but produces a new outcome which in turn is pushed back into the measurement stack by the cpu. The cpu then returns an empty Kernel as the result of the evaluation. A decoder can be used in a quantum program as other classical functions:

allocate q1 q2 q3:
measure
>> vote

The outcome of this program will be 0: the first three measurments were consumed by vote invocation, whose return value is then pushed back to the measurements stack and becomes the only result left in the stack when the program completes.

The measurement stack makes it possible to chain classical functions. This is how majority vote would work with 3 blocks of 3 qubits:

allocate q1 q2 q3:
measure >> vote
allocate q1 q2 q3:
measure >> vote
allocate q1 q2 q3:
measure >> vote
---
>> vote

The outcome of this program would still be just 0.

Repeat-until-success

This is a common quantum pattern where a quantum instruction is repeated until the measurement of some ancilla qubit returns a specific value:

allocate a:
measure
>> loop

and a loop function like:

def loop(m0):
  if m0 == 0:
    return Kernel.allocate('a', compute=[H('a')], callback=Loop())

This program will keep running until the measurement of the qubit returns 1.

Layers, compilers & stacks.

A layer defines the instruction set available to a program, including both quantum and classical instructions.

layer                   :== quantum_definitions; classic_definitions
quantum_definitions     :== quantum_definition
                          | quantum_definition quantum_definitions
classic_definitions     :== classic_definition
                          | classic_definition classic_definitions
quantum_definition      :== op target_length matrix
classic_definition      :== op callback
target_length           :== int
callback                :== (outcomes) -> (kernel | outcome | None)
outcomes                :== None
                          | outcome
                          | outcome outcomes
outcome                 :== 1 | 0

As part of the definition of a quantum instruction it must include its matrix that define its semantics. This enables the automatic creation of a classical emulator and validation tools for the layer.

On the other hand, classical instructions are defined by classical callback method that given a list of outcomes, it returns either a kernel, another outcome, or nothing.

A compiler transforms a program from one layer to another. It converts quantum instructions while preserving their semantics and retains classical instruction invocations with the same parameters. It may add new classical instructions as needed.

A stack is an ordered list of layers and compilers, where the top and bottom elements are always layers, and a compiler exists between each pair of layers.

stack           :== base_layer
base_layer      :== layer_node
layer_node      :== layer
                :== layer compiler_node
compiler_node   :== compiler layer_node

A quantum program is comprised of a stack and a list of kernels. We enhance qstack grammar to incorporate this:

program         :== stack; kernels

All quantum instructions in the program belong to the base layer, while classical instructions can originate from any layer. The stack is specified in the syntax via a @stack attribute:

@stack: cliffords

allocate: q1 q2
  h q1
  cx q1 q2
measure

Quantum Machine

A quantum machine is a device capable of evaluating quantum programs. It consists of two processing units:

• quantum processing unit (qpu): to process quantum instructions:

qpu       :== restart allocate eval measure
restart   :== () -> ()
allocate  :== (qubit_id) -> ()
eval      :== (quantum_instruction) -> ()
measure   :== () -> (outcome)

• classical processing unit (cpu): to process classical instructions:

cpu       :== restart collect eval consume
restart   :== () -> ()
collect   :== (outcome) -> ()
eval      :== (classical_instruction) -> (kernel)
consume   :== () -> (outcome)

To evaluate a single shot of a program:

1. The quantum machine calls restart on both cpu and qpu.
2. It evaluates in order each one of the kernels as follows:
   1. it allocates the target qubit in the qpu
   2. it iterates through each instruction:
      1. if a quantum instructions, it delegates evaluates to the qpu
      2. if an embedded kernel, it recursively evaluates the kernel
   3. it measures the target qubit in the qpu
   4. if the kernel has a classical instruction, it delegates its evaluation to the cpu. 1.it then recursively evaluates the kernel returned from the cpu evaluation.

---

IGNORE... old stuff...

Error correction layer

An error correction layer accepts the list of encoded instruction supported by an error correction code, and generates gadgets implemented in terms of an output instruction set, typically the set of clifford instructions. For example, the outcome of evaluating program (1) with an error correction layer based on the repetition code would be similar to:

allocate: q0.0 q0.1 q0.2 q1.0 q1.1 q1.2
  allocate: a0 a1
    cx q0.0 a0
    cx q0.1 a1
    cx q0.1 a0
    cx q0.2 a1
  measure
  ---
  allocate: a0 a1
    cx q1.0 a0
    cx q1.1 a1
    cx q1.1 a0
    cx q1.2 a1
  measure
  ---
  h q0.0
  h q0.1
  h q0.2
  ---
  ...
measure

Noise layer

A noise layer emulates noise on a device by adding random instructions based on a noise model. For example, a pauli-noise layer will add random Pauli instructions to a program with some probability.

Physical layer

A physical layer is used for executing instructions on an emulator or QPU. A physical layer accepts instructions from an input instruction set and generates empty gadgets, therefore it has an empty output instruction set.

In a physical layer, each block corresponds to an individual qubit.

Physical layers can be generated from any other layer by taking a layer's output instruction set and building the corresponding state-vector emulator that accepts the same list of instructions and applies their corresponding action.

Layer design

A layer implements the following methods:

• allocate(block_ids): assign a block to the given ids
• measure(block_ids): measures and unassigns the corresponding blocks ids, returns the measured values.
• eval(instructions): evaluates the given instructions. The outcome of eval is is a list of gadgets.

Gadgets

A gadget represents a unit of hybrid execution in a quantum processor. It is comprised of:

1. kernel: a kernel to be evaluated by a layer
2. continuation: an optional method that given the list of outcomes from the kernel's measurements, returns a new gadget.

Stack

Instructions are evaluated in the context of a quantum stack. A stack is comprised of an ordered list of layers.

A stack is said to be valid if for all layers in the stack, each instruction in the ouput instruction set is an instruction of the input instrction set of the next layer in the stack.

$L_{n}.\text{O} \subset L_{n+1}.\text{I}$

Encoding quantum programs

Encoding is the process of evaluating a quantum program through the layers of a quantum stack, and report back the list of instructions generated by the lowest non-physical level.

Well-formness

A quantum program is said to be well formed if for every block used in the program it maintains the block's life-cycle.

Theorem: a quantum program remains well-formed after getting encoded through a valid quantum stack.

Evaluating quantum programs:

A stack evaluates a list of instructions and report their measurements by recursively evaluating them on each layer as follows:

1. It identifies all prepare instructions and call allocate on the current layer with the correspond block_ids.
2. It calls evaluate on the current layer.
3. If evaluate returns a gadget, it evaluates the gadget as follows:
   • It creates a new stack by removing the top layer from this stack
   • It evaluates the gadget's list of instructions with the new stack
   • It invokes the gadget's continuation it with the outcome of the previous evaluation
   • It keeps evaluating the resulting gadget with the same layer until no more gadgets are returned
4. It identies all measure instructions, and calls measure on the current layer with the correspond block_ids.
5. Returns the outcomes from measure

def eval_kernel(kernel, stack):
  layer = stack.layers[0]

  if kernel.blocks:
    layer.allocate(kernel.blocks)

  for gadget in layer.eval(instructions):
    eval_gadget(gadget, stack.layers[1:])

  if kernel.blocks:
    return layer.measure(kernel.blocks)
  else:
    return None


def eval_gadget(gadget, stack):
  if gadget is None :
    return
  else:
    outcomes = eval_kernel(gadget.kernel, stack)
    cont_gadget = gadget.continuation(outcomes)
    eval_gadget(cont_gadget, stack)