Quantum computation promises exponential or polynomial speedups over classical computation for a wide range of problems, including integer factoring, quantum chemistry, and linear-system solving.However, current quantum devices remain too noisy to execute complex algorithms reliably.Overcoming this noise and achieving quantum advantage require a fault-tolerant quantum computer (FTQC).The resource overhead associated with fault-tolerant operation is substantial, and reducing this overhead remains one of the central challenges.A major source of this overhead arises from the implementation of non-Clifford gates, which are essential for universal quantum computation.A non-Clifford gate such as the T gate is implemented using a special quantum state known as a magic state, which is prepared via a process called magic state distillation.Magic state distillation is resource-intensive and remains a major bottleneck in FTQC.Hence, reducing the distillation overhead is necessary to lower the overall FTQC overhead.The large overhead of magic state distillation has significantly influenced FTQC architectures.In particular, it has motivated compilation schemes optimized under the constraint of expensive magic state distillation.While reducing the distillation overhead is crucial, it is not sufficient; lowering the overall FTQC overhead also requires revisiting design choices guided by this constraint.Therefore, efficient methods are required not only for preparing magic states but also for consuming them.In this thesis, we reduce the overhead of fault-tolerant quantum computation by focusing on the preparation and consumption of magic states.In contrast to traditional logical-level distillation, physical-level distillation allows direct implementation with physical gates and has the potential to drastically reduce the distillation overhead.However, existing physical-level distillation protocols, such as zero-level distillation, cannot directly yield high-fidelity magic states.We propose two magic state distillation protocols that use physical-level distillation techniques to efficiently prepare high-fidelity magic states.The first protocol is a two-level distillation protocol using physical-level distillation as the first-level stage.The second protocol utilizes lattice surgery to reduce the spacetime overhead of a physical-level distillation protocol.The former targets a high-fidelity regime, whereas the latter targets an intermediate-fidelity regime-lower than the former, but higher than zero-level distillation.Next, we investigate FTQC architectures that can efficiently consume the magic states prepared by these protocols.Because magic state distillation is probabilistic, occasional failures can delay computation.Moreover, physical-level distillation protocols generally exhibit higher failure probabilities than logical-level ones.This delay is amplified by parallel execution, making it an i ii important consideration for FTQC using physical-level distillation protocols.We therefore propose a scheme to mitigate the negative performance impact caused by magic state distillation failures by introducing a pool of magic states for each distillation factory.The proposed distillation protocols allow the simultaneous preparation of many magic states.Leveraging this capability, we propose an FTQC compilation scheme optimized for highly parallel quantum algorithms.By performing magic state distillation locally and consuming magic states in parallel, the scheme enables highly parallel execution and consequently reduces the computational time overhead.Overall, this thesis presents a unified approach to reducing the overhead of fault-tolerant quantum computation.By improving both the preparation and consumption of magic states, it advances the design of resource-efficient FTQC architectures.These results demonstrate that efficient magic state preparation motivates efficient magic state consumption, and vice versa.Together, they bring us closer to the practical realization of fault-tolerant quantum computers.
Quantum computation promises exponential or polynomial speedups over classical computation for a wide range of problems, including integer factoring, quantum chemistry, and linear-system solving.However, current quantum devices remain too noisy to execute complex algorithms reliably.Overcoming this noise and achieving quantum advantage require a fault-tolerant quantum computer (FTQC).The resource overhead associated with fault-tolerant operation is substantial, and reducing this overhead remains one of the central challenges.A major source of this overhead arises from the implementation of non-Clifford gates, which are essential for universal quantum computation.A non-Clifford gate such as the T gate is implemented using a special quantum state known as a magic state, which is prepared via a process called magic state distillation.Magic state distillation is resource-intensive and remains a major bottleneck in FTQC.Hence, reducing the distillation overhead is necessary to lower the overall FTQC overhead.The large overhead of magic state distillation has significantly influenced FTQC architectures.In particular, it has motivated compilation schemes optimized under the constraint of expensive magic state distillation.While reducing the distillation overhead is crucial, it is not sufficient; lowering the overall FTQC overhead also requires revisiting design choices guided by this constraint.Therefore, efficient methods are required not only for preparing magic states but also for consuming them.In this thesis, we reduce the overhead of fault-tolerant quantum computation by focusing on the preparation and consumption of magic states.In contrast to traditional logical-level distillation, physical-level distillation allows direct implementation with physical gates and has the potential to drastically reduce the distillation overhead.However, existing physical-level distillation protocols, such as zero-level distillation, cannot directly yield high-fidelity magic states.We propose two magic state distillation protocols that use physical-level distillation techniques to efficiently prepare high-fidelity magic states.The first protocol is a two-level distillation protocol using physical-level distillation as the first-level stage.The second protocol utilizes lattice surgery to reduce the spacetime overhead of a physical-level distillation protocol.The former targets a high-fidelity regime, whereas the latter targets an intermediate-fidelity regime-lower than the former, but higher than zero-level distillation.Next, we investigate FTQC architectures that can efficiently consume the magic states prepared by these protocols.Because magic state distillation is probabilistic, occasional failures can delay computation.Moreover, physical-level distillation protocols generally exhibit higher failure probabilities than logical-level ones.This delay is amplified by parallel execution, making it an i ii important consideration for FTQC using physical-level distillation protocols.We therefore propose a scheme to mitigate the negative performance impact caused by magic state distillation failures by introducing a pool of magic states for each distillation factory.The proposed distillation protocols allow the simultaneous preparation of many magic states.Leveraging this capability, we propose an FTQC compilation scheme optimized for highly parallel quantum algorithms.By performing magic state distillation locally and consuming magic states in parallel, the scheme enables highly parallel execution and consequently reduces the computational time overhead.Overall, this thesis presents a unified approach to reducing the overhead of fault-tolerant quantum computation.By improving both the preparation and consumption of magic states, it advances the design of resource-efficient FTQC architectures.These results demonstrate that efficient magic state preparation motivates efficient magic state consumption, and vice versa.Together, they bring us closer to the practical realization of fault-tolerant quantum computers.
Magic state distillation (MSD) is an essential element for universal fault-tolerant quantum computing, which distills a high-fidelity magic state from noisy magic states using ideal (error-corrected) Clifford operations. For ideal Clifford operations, it needs to be performed on the logical qubits and hence incurs a large spatiotemporal overhead, which is one of the major bottlenecks for the realization of fault-tolerant quantum computers (FTQCs). Here we propose zero-level distillation, which prepares a high-fidelity logical magic state at the physical level, namely , using physical qubits and nearest-neighbor two-qubit gates on a square lattice. We develop a zero-level distillation circuit and show that distillation can be made even more efficient than the conventional sophisticated approaches with logical level distillations. The key idea involves the Knill -type distillation using the Steane code and its careful mapping to the square-lattice architecture with error detection. The distilled magic state on the Steane-code state is then teleported or converted to surface codes. We numerically find that the error rate of the logical magic state scales as approximately 100 × p 2 in terms of the physical error rate p . For example, with a physical error rate of p = 10 − 4 ( 10 − 3 ), the logical error rate is reduced to p L = 10 − 6 ( 10 − 4 ), resulting in an improvement of 2 (1) orders of magnitude. This contributes to reducing both space and time overhead for early FTQC as well as full-fledged FTQC combined with conventional multilevel distillation protocols.
Fault-tolerant implementation of non-Clifford gates is a major challenge for achieving universal fault-tolerant quantum computing with quantum error-correcting codes. Magic state distillation is the most well-studied method for this but requires significant resources. Hence, it is crucial to tailor and optimize magic state distillation for specific codes from both logical- and physical-level perspectives. In this work, we perform such optimization for two-dimensional color codes, which are promising due to their higher encoding rates compared to surface codes, transversal implementation of Clifford gates, and efficient lattice surgery. We propose two carefully designed distillation schemes based on the 15-to-1 distillation circuit and lattice surgery, differing in their methods for handling faulty rotations. Our first scheme employs faulty T measurement, achieving infidelities of O ( p 3 ) for physical noise strength p . To achieve lower infidelities, our second scheme integrates distillation with “cultivation” (a distillation-free approach to fault tolerantly prepare magic states through transversal Clifford measurements). Our second scheme achieves significantly lower infidelities (e.g., approximately 2 × 10 − 16 at p = 10 − 3 ), surpassing the capabilities of both cultivation and single-level distillation. Notably, to reach a given target infidelity, our schemes require approximately 2 orders of magnitude fewer resources than the previous best magic-state-distillation schemes for color codes.
Zero-level CCZ Distillation
Magic state distillation is a key component of fault-tolerant quantum computation, as it enables the implementation of non-Clifford gates such as the T gate and the CCZ gate via gate teleportation. However, conventional distillation protocols require a large number of logical qubits and introduce substantial spatial and temporal overhead, posing a significant bottleneck for scalable fault-tolerant quantum computation. In this work, we propose a zero-level distillation protocol that efficiently generates a high-fidelity logical CCZ magic state using only physical qubits on a two-dimensional square lattice with nearest-neighbor interactions. Our method leverages the transversal T/T† operation of the [[8,3,2]] code to fault-tolerantly encode the state CCZ∣+++⟩, which is subsequently teleported to three surface-code logical qubits via lattice surgery. To enable teleportation between codes with different distances, we introduce adaptively initialized teleportation (AIT), a tailored initialization procedure for the surface code. Numerical simulations demonstrate that the logical error rate scales as pL≃300×p2 with respect to the physical error rate p. For example, the proposed method improves the logical error rate by approximately one and two orders of magnitude at p=10−3 and p=10−4, respectively, compared to conventional seven-T-gate approaches. The distillation circuit requires only 22 physical qubits, 3 logical qubits, and a circuit depth of 24, reducing the space-time overhead by a factor of approximately 5-10 compared to previous methods. This result highlights the practicality of CCZ-state distillation in early fault-tolerant quantum computation and offers a new direction toward resource-efficient physical-level magic state distillation beyond conventional T-state generation.
Practical quantum computation requires high-fidelity instruction executions on qubits. Among them, Clifford instructions are relatively easy to perform, while non-Clifford instructions require the use of magic states. This makes magic state distillation a central procedure in fault-tolerant quantum computing. A magic state distillation factory consumes many low-fidelity input magic states and produces fewer, higher-fidelity states. To reach high fidelities, multiple distillation factories are typically chained together into a multi-level pipeline, consuming significant quantum computational resources. Our work optimizes the resource usage of distillation pipelines by introducing a novel dynamic pipeline architecture. Observing that distillation pipelines consume magic states in a burst-then-steady pattern, we develop dynamic factory scheduling and resource allocation techniques that go beyond existing static pipeline organizations. Dynamic pipelines reduce the qubit cost by 16%-70% for large-scale quantum applications and achieve average reductions of 26%-37% in qubit-time volume on generated distillation benchmarks compared to state-of-the-art static architectures. By significantly reducing the resource overhead of this building block, our work accelerates progress towards the practical realization of fault-tolerant quantum computers.
Magic state distillation plays an important role in universal fault-tolerant quantum computing, and its overhead is one of the major obstacles to realizing fault-tolerant quantum computers. Hence, many studies have been conducted to reduce this overhead. Among these, Litinski has provided a concrete assessment of resource-efficient distillation protocol implementations on the rotated surface code. On the other hand, recently, Itogawa et al. have proposed zero-level distillation, a distillation protocol offering very small spatial and temporal overhead to generate relatively low-fidelity magic states. While zero-level distillation offers preferable spatial and temporal overhead, it cannot directly generate high-fidelity magic states since it only reduces the logical error rate of the magic state quadratically. In this study, we evaluate the spatial and temporal overhead of two-level distillation implementations generating relatively high-fidelity magic states, including ones incorporating zero-level dis-tillation. To this end, we introduce (0+ 1)-level distillation, a two-level distillation protocol which combines zero-level distillation and the 15-to-1 distillation protocol. We refine the second-level 15-to-l implementation in it to capitalize on the small footprint of zero-level distillation. Under conditions of a physical error probability of Pphys = 10-4(10-3) and targeting an error rate for the magic state within [5 × 10-17,10-11] ([5 × 10-11,10-8]), (0+1)-level distillation reduces the spatiotemporal overhead by more than 63% (61%) compared to the (15-to-l)x(15-to-l) protocol and more than 43% (44%) compared to the (15-to-l)x(20-to-4) protocol, offering a substantial efficiency gain over the traditional protocols.
Near-term FTQC system designs are constrained by limited error budgets and largely sequential execution of non-Clifford gates. As a result, reducing the number of the most-error prone instructions becomes critical for successful program execution. In this work, we study the extractor architecture, a recently proposed FTQC design that enables universal quantum computation on spatially-efficient QEC codes such as the BB code family. In these architectures, over 90% of the total program error arises from the synthillation process, which involves ∣T⟩-state preparation and injection to implement non-Clifford gates. We observe that standard Rz synthillation requires multiple sequential ∣T⟩-state injections, each incurring an inter-module measurements, the most expensive instruction in the architecture, which cumulatively dominate the overall error budget.
To address this bottleneck, we propose INJEQT, a 2-factory design that uses an auxiliary code capable of synthesizing Rz(θ) states with lower error rates. These states are then injected into the extractor modules using only a constant number of inter-module measurements. This approach reduces overall error rates by up to 22×. We further reduce the time overhead by a pre-fetching strategy that prepares the Rz states and their correction states in parallel. This approach improves the wall-clock time by up to 13× and reduces the space-time cost by up to 7.2×, for an optimal choice of the number of INJEQT factories for each metric. We evaluate INJEQT for multiple state preparation techniques such as distillation, cultivation and STAR, and model the execution times for both lattice surgery-based and transversal CNOT based injections. Our results demonstrate that INJEQT is robust across factory choices and device technologies, enabling more efficient architectural designs for FTQC.