Fault-tolerant syndrome extraction is a key ingredient in implementing fault-tolerant quantum computation. While conventional methods use a number of extra qubits that are linear in the weight of the syndrome, several improvements have been introduced using flag gadgets. In this work, we develop a framework to design flag gadgets using classical codes. Using this framework, we show how to perform fault-tolerant syndrome extraction for any stabilizer code with arbitrary distance using exponentially fewer qubits than conventional methods when qubit measurement and reset are relatively slow compared to a round of error correction. In particular, our method requires only ( 2 t + 1 ) t ⌈ log 2 ( w ) ⌉ flag qubits to fault-tolerantly measure a weight- w stabilizer. We further take advantage of the saving provided by our construction to fault-tolerantly measure multiple stabilizers using a single gadget and show that it maintains the same exponential advantage when it is used to fault-tolerantly extract the syndromes of quantum low-density parity-check codes. Using the developed framework, we perform computer-assisted search to find several small examples where our constructions reduce the number of qubits required. These small examples may be relevant to near-term experiments on small-scale quantum computers. Published by the American Physical Society 2024
Fault-tolerant syndrome extraction is a key ingredient in implementing fault-tolerant quantum computation. While conventional methods use a number of extra qubits that are linear in the weight of the syndrome, several improvements have been introduced using flag gadgets. In this work, we develop a framework to design flag gadgets using classical codes. Using this framework, we show how to perform fault-tolerant syndrome extraction for any stabilizer code with arbitrary distance using exponentially fewer qubits than conventional methods when qubit measurement and reset are relatively slow compared to a round of error correction. In particular, our method requires only ( 2 t + 1 ) t ⌈ log 2 ( w ) ⌉ flag qubits to fault-tolerantly measure a weight- w stabilizer. We further take advantage of the saving provided by our construction to fault-tolerantly measure multiple stabilizers using a single gadget and show that it maintains the same exponential advantage when it is used to fault-tolerantly extract the syndromes of quantum low-density parity-check codes. Using the developed framework, we perform computer-assisted search to find several small examples where our constructions reduce the number of qubits required. These small examples may be relevant to near-term experiments on small-scale quantum computers. Published by the American Physical Society 2024
Conventional fault-tolerant quantum error-correction schemes require a number of extra qubits that grow linearly with the code's maximum stabilizer generator weight.For some common distance-three codes, the recent "flag paradigm" uses just two extra qubits.Chamberland and Beverland [Quantum 2, 53 (2018)] provide a framework for flag error correction of arbitrary-distance codes.However, their construction requires conditions that only some code families are known to satisfy.We give a flag error-correction scheme that works for any stabilizer code, unconditionally.With fast qubit measurement and reset, it uses ≤d + 1 extra qubits for a distance-d code.
Quantum computation promises asymptotic speedups over classical algorithms, but realizing these advantages requires overcoming the noisiness of quantum hardware. Although fault-tolerant error correction can allow for reliable quantum computation even using unreliable components, the resource overheads required can substantially erode the asymptotic performance gains. This dissertation focuses on constructing and optimizing fault-tolerant procedures with lower overhead than previous methods were capable of. We present new frameworks for fault-tolerant syndrome extraction using flag gadgets with exponentially reduced ancilla requirements, explicit measurement schedules that achieve asymptotically fewer measurements than stabilizer generators, and a general method for making arbitrary Clifford circuits fault tolerant. In addition, we optimize surface code measurement schedules in the presence of constraints imposed by fabrication defects to reduce logical error rate. Together, these results advance low-overhead fault tolerance and improve performance in resource-constrained and near-term quantum computing settings.
We reduce the extra qubits needed for two fault-tolerant quantum computing protocols: error correction, specifically syndrome bit measurement, and cat state preparation. For distance-three fault-tolerant syndrome extraction, we show an exponential reduction in qubit overhead over the previous best protocol. For a weight- w stabilizer, we demonstrate that stabilizer measurement tolerating one fault needs at most ⌈log2w⌉+1 ancilla qubits. If qubits reset quickly, four ancillas suffice. We also study the preparation of entangled cat states, and prove that the overhead for distance-three fault tolerance is logarithmic in the cat state size. These results apply both to near-term experiments with a few qubits, and to the general study of the asymptotic resource requirements of syndrome measurement and state preparation.With a flag qubits, previous methods use O(a) flag patterns to identify faults. In order to use the same flag qubits more efficiently, we show how to use nearly all 2a possible flag patterns, by constructing maximal-length paths through the a -dimensional hypercube.
We reduce the extra qubits needed for two fault-tolerant quantum computing protocols: error correction, specifically syndrome bit measurement, and cat state preparation. For fault-tolerant syndrome extraction, we show an exponential reduction in qubit overhead over the previous best protocol. For a weight-w stabilizer, we demonstrate that stabilizer measurement tolerating one fault (distance-three) needs at most ⌈ log₂ w ⌉ + 1 ancillas. If qubits reset quickly, four ancillas suffice. We also study the preparation of cat states, simple yet versatile entangled states. We prove that the overhead needed for distance-three fault tolerance is only logarithmic in the cat state size. These results could be useful both for near-term experiments with a few qubits, and for the general study of the asymptotic resource requirements of syndrome measurement and state preparation. For 'a' measured flag bits, there are 2^a possible flag patterns that can identify faults. Hence our results come from solving a combinatorial problem: the construction of maximal-length paths in the a-dimensional hypercube, corresponding to maximal-weight stabilizers or maximal-weight cat states.
Quantum computation holds the promise of solving certain complex problems exponentially faster than classical computers. However, the high prevalent noise in current quantum devices impedes the accurate execution of even basic algorithms. This can be remedied by protecting quantum information with a quantum error-correcting code, where the logical information of an algorithmic qubit is spread across multiple physical qubits. Individual quantum errors are then located and corrected by the fault-tolerant measurement of multi-qubit stabilizer operators (parity checks). Unfortunately, error correction and fault tolerance both impose large demands on the qubit overhead: hundreds to thousands of physical qubits per logical qubit.
We reduce the spacetime cost of fault tolerance by redesigning key building blocks of an error-corrected quantum computer. First, we develop a combinatorial proof with flag fault tolerance that exponentially reduces the extra qubits needed to measure a stabilizer of any size, while tolerating one fault. We leverage these proofs to then design state preparation circuits for the Steane and Golay codes with 100% yield. Next, we improve error correction on a planar layout by showing that a distance-four code encoding six logical qubits protects information as well as the distance-five surface code, using one-tenth as many physical qubits. Finally, we optimize the time overhead of logical gates in surface code quantum computers by protecting measurement results with a classical code, cutting computation time by a factor of two to six. Our hardware-agnostic optimizations of fault tolerance overheads thus suggest new routes to advance the timeline of error-free quantum computing.
Flag-style fault-tolerance has become a linchpin in the realization of small fault-tolerant quantum-error correction experiments. The flag protocol's utility hinges on low qubit over-head, which is typically much smaller than in other approaches. However, as in most fault-tolerance protocols, the advantages of flag-style error correction come with a tradeoff: fault tolerance can be guaranteed, but such protocols involve high-depth circuits, due to the need for repeated stabilizer measurements. Here, we demonstrate that a dynamic choice of stabilizer measurements, based on past syndromes, and the utilization of elements from the full stabilizer group, leads to flag protocols with lower-depth syndrome-extraction circuits for the [[5], [1], [3]] code, as well as for the Steane code when compared to the standard methods in flag fault tolerance. We methodically prove that our new protocols yield fault-tolerant lookup tables, and demonstrate them with a pseudothreshold simulation, showcasing large improvements for all protocols when compared to previously-established methods. This work opens the dialogue on exploiting the properties of the full stabilizer group for reducing circuit overhead in fault-tolerant quantum-error correction.