Parallel Logical Measurements via Quantum Code Surgery

This paper presents a fault-tolerant code surgery scheme for any qubit stabilizer LDPC code that enables the parallel measurement of many logical Pauli operators in $O(d)$ time using a scalable number of ancilla qubits, while preserving the code's LDPC property and fault-distance without requiring costly ancillary logical codeblocks.

The Gist

The Big Picture: Fixing a Leaky Boat While Sailing

Imagine you are trying to steer a massive, fragile boat (a quantum computer) across a stormy ocean. The boat is prone to leaks (errors). To keep it afloat, you have a crew of workers constantly patching holes (error correction).

Sometimes, you need to check specific parts of the boat to see if you are on the right course. In quantum computing, this is called a logical measurement. However, checking one part often disturbs the whole boat. If you try to check too many parts at once, the boat might sink because the workers get in each other's way.

This paper introduces a new, highly efficient way for the crew to check many different parts of the boat simultaneously without causing a crash, even when the boat is very large and complex.

The Problem: The "Crowded Kitchen"

Think of the quantum computer's data as ingredients in a very crowded kitchen.

• The Old Way (CKBB Scheme): If you wanted to chop onions (measure one logical operator) and dice carrots (measure another), you had to use a huge, separate cutting board for each task. If you wanted to chop 10 things, you needed 10 huge cutting boards. This took up too much space (ancilla qubits) and was slow.
• The Parallel Problem: In modern, high-speed quantum codes (called LDPC codes), the "ingredients" (data qubits) are often mixed together. If you try to chop onions and carrots at the same time, your knives might hit the same ingredient, causing a mess (errors). Previous methods could only chop one type of ingredient at a time or required extra, expensive "helper ingredients" (ancilla logical states) to make it work.

The Solution: "Code Surgery" with a Smart Assembly Line

The authors propose a new method called Parallel Logical Measurements via Quantum Code Surgery. They combine three clever tricks to solve the crowded kitchen problem:

1. The "Copy Machine" (Brute-Force Branching)

Imagine you have a messy pile of papers (logical operators) that are all tangled together on the same desk. You can't read them all at once.

• The Trick: Instead of trying to untangle them on the desk, you use a "copy machine" to make clean, separate copies of each paper and place them on different, empty desks (ancilla qubits).
• The Result: Now, instead of one crowded desk, you have a row of desks, each with one clear paper. You can read them all at the same time without them interfering with each other. The paper calls this "Brute-Force Branching."

2. The "Lightweight Scaffold" (Gauging Measurement)

Once the papers are on separate desks, you need to read them without tearing them up.

• The Trick: The authors use a very lightweight, efficient scaffold (an "expander graph") to hold the papers while they are being read. Previous methods used heavy, bulky scaffolds that took up a lot of space. This new scaffold is minimal and only adds a tiny bit of extra material.
• The Result: You can read the papers (measure the qubits) with very little extra cost in space.

3. The "Universal Adapter" (Connecting the Dots)

Sometimes you don't just want to read one paper; you want to read a combination, like "The sum of Paper A and Paper B."

• The Trick: The authors use "adapters" to connect the separate desks together just enough to measure the combination, but not so much that they get tangled again.
• The Result: You can measure complex combinations of ingredients (Pauli products) all at once, even if they are different types (like mixing X, Y, and Z measurements).

Why This is a Big Deal

The paper claims three major improvements over previous methods:

1. Massive Space Savings:

   • Old Way: If you wanted to measure $t$ things, you might need space proportional to $t^2$ or $t \times d$ (where $d$ is the size of the boat).
   • New Way: You only need space proportional to $t \times \log(t)$. It's like going from needing a warehouse for 100 items to needing a single closet.
   • Analogy: If the old method was like building a separate house for every guest, this method is like setting up a single, efficient hotel where everyone has their own room but shares the same hallway.

2. No "Magic" Ingredients Needed:

   • Some previous methods required special, hard-to-make "magic states" (like a specific type of rare spice) to measure certain combinations.
   • New Way: This method can measure any combination (including tricky "Y" terms) without needing those rare ingredients. It just uses the standard ingredients you already have.

3. Speed Independence:

   • The time it takes to do the surgery doesn't get slower just because you have more items to measure. Whether you measure 2 items or 1,000 items, the process takes roughly the same amount of time (specifically, time proportional to the code distance $d$).

The Bottom Line

The authors have built a "universal adapter" for quantum computers. They figured out how to take a messy, overlapping set of tasks, copy them onto separate, clean workspaces, and measure them all in parallel using very little extra space and no special "magic" ingredients.

This makes it much more feasible to run large-scale, fault-tolerant quantum computers in the future, as it removes a major bottleneck (the need for too much extra space) that was stopping us from doing complex calculations efficiently.

Technical Summary

Technical Summary: Parallel Logical Measurements via Quantum Code Surgery

Problem Statement

Topological codes, such as surface codes, have been the primary candidates for fault-tolerant quantum computation but suffer from low encoding rates, leading to significant space overhead. Quantum Low-Density Parity Check (LDPC) codes offer higher rates and lower overhead but require new techniques for logical computation. While methods like transversal gates and homomorphic measurements exist, they are often restricted to specific code structures or topological codes.

Generalized code surgery allows for logical Pauli measurements on any LDPC code by deforming the code (gauge-fixing) to decompose logical operators into stabilizers. However, a persistent challenge has been parallelization. Existing surgery schemes struggle to measure multiple logical operators simultaneously, particularly when the logical operators overlap on physical data qubits—a common scenario in high-rate LDPC codes. Previous attempts to parallelize measurements, such as those by Zhang & Li [46], relied on the CKBB scheme [28], resulting in space overheads that are at least quadratic in the code distance $d$ (e.g., $O(t^2 \omega d)$ or $O(t \omega (\log t + d))$). Furthermore, these schemes often required ancillary logical states (e.g., $|Y\rangle$ states) or were restricted to CSS codes, limiting their applicability and efficiency.

Methodology

The authors propose a code surgery scheme applicable to any qubit stabilizer LDPC code that fault-tolerantly measures a collection of logically disjoint Pauli product operators in parallel. The scheme combines three key elements from recent literature:

1. Brute-Force Branching: To handle overlapping logical operators, the scheme employs "brute-force branching" [46]. This process uses a tree of hypergraph product patches (branching stickers) to separate logical operators with overlapping support onto disjoint leaves. This ensures that operators to be measured have disjoint physical support, a prerequisite for efficient parallel measurement.
2. Gauging Logical Measurements: Instead of the CKBB scheme, the authors utilize the gauging measurement framework [39, 40]. This involves appending expander graphs to the leaves of the branching tree to perform the measurement. This approach guarantees that the deformed code remains LDPC and provides rigorous fault-tolerance guarantees without requiring the code to be a subsystem code.
3. Universal Adapters: To measure products of logical operators (e.g., $\bar{X}_1 \otimes \bar{Z}_2$), the scheme uses universal adapters [45] to connect the ancillary systems of disjoint logical operators. This allows for the measurement of Pauli products while maintaining the LDPC property and fault-distance.

Handling Non-CSS and Mixed Bases:
A critical innovation is the ability to measure mixed-type operators (including $\bar{Y}$) on non-CSS stabilizer codes without ancillary logical qubits. The authors utilize a specific logical basis (standard form [49]) where $\bar{X}$ and $\bar{Z}$ representatives have controlled overlap properties. By applying local Clifford transformations (conceptually, not physically) to align the basis, they can branch arbitrary Pauli operators (including $\bar{Y}$) simultaneously. The branching process converts all representatives into products of $Z$ Paulis on the leaves, which are then measured via gauging.

Arbitrary Commuting Sets:
For arbitrary commuting sets of Pauli products (where operators may overlap on logical qubits), the scheme extends the procedure using "twist-free surgery" techniques [48, 46]. This involves decomposing products into $X$ and $Z$ components, potentially requiring ancillary logical $|0\rangle$ and $|Y\rangle$ states. However, the authors note that their ability to measure $\bar{Y}$ operators directly in parallel significantly reduces the overhead for preparing these ancillary states compared to previous methods.

Key Contributions and Results

1. Space and Time Complexity

For a collection of $t$ logically disjoint Pauli product measurements supported on $t$ logical qubits, with a maximum single logical Pauli representative weight of $\omega$ (where $\omega \ge d$):

• Space Overhead: The scheme uses $O(t\omega(\log t + \log^3 \omega))$ ancilla qubits.
  • The $O(t\omega \log t)$ term arises from brute-force branching.
  • The $O(t\omega \log^3 \omega)$ term arises from the gauging measurement (specifically, the decongestion of expander graphs).
• Time Overhead: The measurement is performed in $O(d)$ time, independent of $t$. This is achieved by performing $d$ rounds of syndrome extraction, which is independent of the number of parallel operations.

2. Preservation of Code Properties

• LDPC Property: The scheme preserves the LDPC property of the original code. Unlike some previous parallel schemes that required moving to subsystem codes or losing sparsity, this method maintains the constant check weight and qubit degree.
• Fault-Distance: The scheme preserves the code distance $d$. It is fault-tolerant with a fault-distance of $d$, assuming at least $d$ rounds of stabilizer measurements are performed during the branching and measurement phases.
• No Ancillary Logical Blocks: The scheme does not require pre-prepared logical ancilla codeblocks (beyond the physical ancilla qubits), addressing a cost issue in schemes that rely on distilling logical states.

3. General Applicability

• Stabilizer Codes: The method applies to general stabilizer codes, not just CSS codes.
• Mixed Operators: It can measure mixed-type operators (containing $\bar{X}$, $\bar{Y}$, and $\bar{Z}$) in parallel without requiring transversal $S$ gates or $|Y\rangle$ state distillation, a limitation of previous parallel schemes [46].

Significance and Claims

The paper claims to address a critical bottleneck in scaling quantum LDPC codes: the efficient parallel measurement of logical operators. By combining brute-force branching with gauging measurements and adapters, the authors achieve:

• Asymptotic Efficiency: The space overhead is significantly lower than the CKBB-based parallel schemes, particularly avoiding the quadratic dependence on $d$ ($O(d^2)$) found in prior work.
• Robustness: The scheme provides rigorous fault-tolerance guarantees without sacrificing the LDPC structure, which is essential for the practical implementation of high-rate quantum memories.
• Flexibility: The ability to measure arbitrary disjoint Pauli products (including $\bar{Y}$) on general stabilizer codes makes the scheme a versatile tool for Pauli-based computation, which, when combined with transversal magic gates or state preparation, enables universal fault-tolerant quantum computation.

The authors acknowledge that while the asymptotic bounds are strong, the constant factors in brute-force branching may be large for low-blocklength codes. They suggest that for finite-size codes, the overhead may be substantially lower than the asymptotic upper bound, as decongestion is often unnecessary in practice. They also note that finding optimal logical bases with minimal representative weights is NP-hard, so the cost is computed in terms of the chosen representative weight $\omega$, which may be larger than the code distance $d$.

In summary, this work presents a scalable, fault-tolerant framework for parallel logical measurements on quantum LDPC codes, overcoming previous limitations regarding space overhead, code type restrictions, and the need for complex ancillary state preparation.