Achieving quantum speedups in practical tasks remains challenging for current noisy intermediate-scale quantum (NISQ) devices. These devices always encounter significant obstacles such as inevitable physical errors and the limited scalability of current near-term algorithms. Meanwhile, assuming a typical architecture for fault-tolerant quantum computing (FTQC), realistic applications inevitably require a vast number of qubits, typically exceeding 10 6 , which seems far beyond near-term realization. In this work, to bridge the gap between the NISQ and FTQC eras, we propose an alternative approach to achieve practical quantum advantages on early-FTQC devices. Our framework is based on partially fault-tolerant logical operations to minimize spatial overhead and avoids the costly distillation techniques typically required for executing non-Clifford gates. To this end, we develop a space-time efficient state preparation protocol to generate an ancillary non-Clifford state consumed for implementing an analog rotation gate with an arbitrary small angle θ and a remarkably low worst-case error rate below O ( | θ | p ph ) , where p ph is the physical error rate. Furthermore, we propose several error suppression schemes tailored to our preparation protocol, which are essential to minimize the overhead for mitigating errors. Based on this framework, we present several promising applications that leverage the potential of our framework, including the Trotter simulation and quantum phase estimation (QPE). Notably, we demonstrate that our framework allows us to perform the QPE for an ( 8 × 8 ) -site Hubbard model with fewer than 6.8 × 10 4 qubits and an execution time of 10.6 days (or 14 min with full parallelization) under p ph = 10 − 4 , which is significantly faster than recent classical estimation with tensor network techniques (density matrix renormalization group and projected entangled pair states).
Achieving quantum speedups in practical tasks remains challenging for current noisy intermediate-scale quantum (NISQ) devices. These devices always encounter significant obstacles such as inevitable physical errors and the limited scalability of current near-term algorithms. Meanwhile, assuming a typical architecture for fault-tolerant quantum computing (FTQC), realistic applications inevitably require a vast number of qubits, typically exceeding 10 6 , which seems far beyond near-term realization. In this work, to bridge the gap between the NISQ and FTQC eras, we propose an alternative approach to achieve practical quantum advantages on early-FTQC devices. Our framework is based on partially fault-tolerant logical operations to minimize spatial overhead and avoids the costly distillation techniques typically required for executing non-Clifford gates. To this end, we develop a space-time efficient state preparation protocol to generate an ancillary non-Clifford state consumed for implementing an analog rotation gate with an arbitrary small angle θ and a remarkably low worst-case error rate below O ( | θ | p ph ) , where p ph is the physical error rate. Furthermore, we propose several error suppression schemes tailored to our preparation protocol, which are essential to minimize the overhead for mitigating errors. Based on this framework, we present several promising applications that leverage the potential of our framework, including the Trotter simulation and quantum phase estimation (QPE). Notably, we demonstrate that our framework allows us to perform the QPE for an ( 8 × 8 ) -site Hubbard model with fewer than 6.8 × 10 4 qubits and an execution time of 10.6 days (or 14 min with full parallelization) under p ph = 10 − 4 , which is significantly faster than recent classical estimation with tensor network techniques (density matrix renormalization group and projected entangled pair states).
Partially fault-tolerant quantum computing (FTQC) has recently emerged as a promising approach for the execution of megaquop-scale circuits with millions of logical operations. In this work, we demonstrate the strengths and the limitations of this approach by conducting quantum resource estimation (QRE) of the space--time-efficient analog rotation (STAR) architecture using realistic hardware specifications for superconducting processors, and compare it against the QRE of the full FTQC architecture. We show how the performance of the STAR architecture's protocols is affected by hardware improvements. We also reduce the space requirements for partial FTQC by developing a procedure leveraging code growth to decrease the size of a factory producing analog rotation states. Our results reveal a non-trivial dependence of the optimal pre-growth code distance on the rotation angle with respect to post-growth infidelity. Further, we analyze space--time trade-offs between the factory size and the error-mitigation overhead, and observe that in an application-agnostic setting, there is a Goldilocks zone for circuits in the regime of roughly 105--106 small-angle rotation gates. We show that quantum simulation of 2D Fermi--Hubbard model systems is a particularly well-suited application for the STAR architecture, requiring only hundreds of thousands of physical qubits and runtimes on the order of minutes for modest system sizes. Due to its favourable algorithmic scaling to larger system sizes, utility-scale simulation of the 2D Fermi--Hubbard model could potentially be attained using partial FTQC.
Quantum computers are expected to drastically accelerate certain computing tasks versus classical computers. Noisy intermediate-scale quantum (NISQ) devices, which have tens to hundreds of noisy physical qubits, are gradually becoming available, but it is still challenging to achieve useful quantum advantages in meaningful tasks. On the other hand, full fault-tolerant quantum computing (FTQC) based on quantum error correction code remains far beyond realization due to its extremely large requirement of high-precision physical qubits. In this study, we propose a quantum computing architecture to close the gap between NISQ and FTQC architectures. Our architecture is based on erroneous arbitrary rotation gates and error-corrected Clifford gates implemented by lattice surgery. We omit the typical distillation protocol to achieve direct analog rotations and small qubit requirements, and minimize the remnant errors of the rotations by a carefully designed state injection protocol. Our estimation based on numerical simulations shows that for early-FTQC devices that consist of 104 physical qubits with physical error probability p=10−4 , we can perform roughly 1.72×107 Clifford operations and 3.75×104 arbitrary rotations on 64 logical qubits. Such computations cannot be realized by the existing NISQ and FTQC architectures on the same device, as well as classical computers. We hope that our proposal and the corresponding development of quantum algorithms based on it will bring new insights into the realization of practical quantum computers in the future. Published by the American Physical Society 2024
Fault-tolerance is the future of quantum computing, ensuring error-corrected quantum computation that can be used for practical applications. Resource requirements for fault-tolerant quantum computing (FTQC) are daunting, and hence, compilation techniques must be designed to ensure resource efficiency. There is a growing need for compilation strategies tailored to the early FTQC regime, which refers to the first generation of fault-tolerant machines operating under stringent resource constraints of fewer physical qubits and limited distillation capacity. Present-day compilation techniques are largely focused on overprovisioning of routing paths and make liberal assumptions regarding the availability of distillation factories. Our work develops compilation techniques that are tailored to the needs of early FTQC systems, including distillation-adaptive qubit layouts and routing techniques. In particular, we show that simple greedy heuristics are extremely effective for this problem, offering up to 60% reduction in the number of qubits compared to prior works. Our techniques offer results with an average overhead of 1.2X in execution time for a 53% reduction in qubits against the theoretical lower bounds. As the industry develops early FTQC systems with tens to hundreds of logical qubits over the coming years, our work has the potential to be widely useful for optimising program executions.
Achieving practical quantum speedup with limited resources is a crucial challenge in both academic and industrial communities. To address this, a partially fault-tolerant quantum computing architecture called “space-time efficient analog rotation quantum computing architecture” (STAR architecture) been recently been proposed. This architecture focuses on minimizing resource requirements while maximizing the precision of non-Clifford gates, essential for universal quantum computation. However, nondeterministic processes such as the repeat-until-success (RUS) protocol and state injection can introduce significant computational overhead. Therefore, optimizing the logical circuit to minimize this overhead by using efficient fault-tolerant operations is essential. This paper presents an efficient method for simulating the time evolution of the two-dimensional (2D) Hubbard-model Hamiltonian, a promising application of the STAR architecture. We present two techniques, the parallel-injection protocol and adaptive injection-region updating, to reduce unnecessary time overhead specific to our architecture. By integrating these with the existing fermionic (f) technique, we develop an efficient Trotter-based time-evolution operation for the 2D Hubbard model. Our analysis reveals an acceleration of over 10 times compared to naive serial compilation. Based on this optimized compilation, we estimate the computational resources required for the quantum phase estimation of the 2D Hubbard model. For devices with a physical error rate of p phys = 10 − 4 , we estimate that approximately 6.2 × 10 4 physical qubits are required to achieve faster ground-state energy estimation of the 8 × 8 Hubbard model compared to classical computation.
Fault tolerance is widely regarded as indispensable for achieving scalable and reliable quantum computing. However, the spacetime overhead required for fault-tolerant quantum computating remains prohibitively large. A critical challenge arises in many quantum algorithms with Clifford + φ compiling, where logical rotation gates RZL(φ) serve as essential components. The Eastin-Knill theorem prevents their transversal implementation in quantum error correction codes and necessitating resource-intensive workarounds through T-gate compilation combined with magic state distillation and injection. In this work, we consider error-structure-tailored fault tolerance, where fault-tolerance conditions are analyzed by combining perturbative analysis of realistic dissipative noise processes with the structural properties of stabilizer codes. Based on this framework, we design 1-fault-tolerant continuous-angle rotation gates in stabilizer codes, implemented via dispersive-coupling Hamiltonians. Our approach could circumvent the need for T-gate compilation and distillation, offering a hardware-efficient solution that maintains simplicity, minimizes physical footprint, and requires only nearest-neighbor interactions. Integrating with recent small-angle-state preparation techniques, we can suppress the gate error to 91∣φ∣p2 for small rotation angle (where p denotes the physical error rate). For current achievable hardware parameters (p=10−3), this enables reliable execution of over 107 small-angle rotations when ∣φ∣≈10−3, meeting the requirements of many near-term quantum applications. Compared to the 15-to-1 magic state distillation and magic state cultivation approaches, our method reduces spacetime resource costs by factors of 1337.5 and 43.6, respectively, for a Heisenberg Hamiltonian simulation task under realistic hardware assumptions.
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.