Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Design of Fault-Tolerant Protocol and Variational Quantum Algorithms for Resource-Efficient Quantum Computation

Shiro Tamiya

Published Mar 21, 2024• 0 citations
Publisher

Abstract

Quantum computing offers promising potential for faster computation compared to classical computing, with the advantage of improved scaling as the problem size increases.Many fast quantum algorithms have been developed to solve specific problems using quantum computation, and they are expected to be applied to a wide range of fields, including quantum chemistry, condensed matter physics, and machine learning.However, the high cost of realizing physical systems to perform quantum computations makes resource-efficient implementation methods indispensable.In the first part of this thesis, we study the resource-efficient design of a fault-tolerant protocol based on quantum low-density parity-check (LDPC) codes.Scalable quantum computation to achieve the speed-ups over classical computation requires fault tolerance due to the vulnerability of quantum systems to noise.Fault-tolerant quantum computation (FTQC) expenses significant space and time overheads to achieve fault-tolerant quantum circuits from the original circuits intended to simulate.An FTQC protocol based on quantum LDPC codes has the attractive advantage of constant-space overhead, but has the disadvantage of requiring a long polynomial-time overhead.In this thesis, we present a polylogarithmic time overhead FTQC protocol based on quantum LDPC code, which is exponentially time efficient compared to conventional protocols while maintaining the advantage of the constant space overhead.This overhead is enjoyed even if the non-zero classical computation performing the decoding algorithms is considered.The second part of this thesis investigates the resource-efficient design of variational quantum algorithms (VQAs).The VQAs are a heuristic algorithm with promising applications in various fields.The VQAs can be performed by minimizing task-specific cost functions, typically defined as the expectation values of observables.However, it is known that the execution of variational quantum algorithms requires numerous quantum measurements, and their reduction is a significant challenge in algorithm implementation.In the first study of this part, we propose a new algorithm for calculating nonadiabatic couplings (NACs), which are important quantities in simulating molecular

DOI
10.15083/0002012831

Related papers

Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation

Hayata Yamasaki, Masato Koashi

Abstract Scalable realization of quantum computing to attain substantial speedups over classical computing requires fault tolerance. Conventionally, protocols for fault-tolerant quantum computation (FTQC) demand excessive space overhead of physical qubits per logical qubit. A more recent protocol to achieve constant-space-overhead FTQC using quantum low-density parity-check (LDPC) codes thus attracts considerable attention but suffers from another drawback: it incurs polynomially long time overhead. To address these problems, we here introduce an alternative approach using a concatenation of multiple small-size quantum codes for the constant-space-overhead FTQC rather than a single large-size quantum LDPC code. We develop techniques for concatenating different quantum Hamming codes with growing sizes. As a result, we construct a low-overhead protocol to achieve constant space overhead and only quasi-polylogarithmic time overhead simultaneously. Our protocol accomplishes FTQC even if a decoder has non-constant runtime, unlike the existing constant-space-overhead protocol. These results establish a foundation for FTQC realizing a large class of quantum speedups within feasibly bounded space overhead yet negligibly short time overhead. This achievement opens a promising avenue for the low-overhead FTQC based on code concatenation.

arXiv:2207.08826•Nature Physics•Jan 16, 2024•54 citations

The Complexity of Quantum Fault Tolerance

Quynh The Nguyen

The theory of fault tolerance is a cornerstone of computing and many modern technologies. With the development of quantum science and engineering, fault tolerance has become increasingly important, as quantum systems are intrinsically susceptible to noise. This thesis presents several advances in quantum fault tolerance and develops new connections between fault tolerance and quantum complexity theory. In Part I, we construct a fault-tolerant quantum computation scheme with constant space overhead and near-logarithmic time overhead. This is the lowest overhead achieved to date and and provides the first rigorous proof that fault tolerance based on quantum low-density parity-check (qLDPC) codes can achieve better asymptotic spacetime overhead than conventional schemes. The construction relies on locally testable qLDPC codes and new quantum state distillation algorithms with improved spacetime overhead. Additionally, a variant of these algorithms yields the first magic state distillation algorithm with constant space overhead. In Part II, we make progress on the quantum probabilistically checkable proofs (PCP) conjecture by using ideas from fault tolerance. We introduce a new circuit-to-Hamiltonian mapping that allows Hamiltonians to inherit the fault tolerance properties of quantum circuits. Using this new mapping, we construct the first known template for quantum locality-preserving gap amplification---the quantum analogue of a central ingredient in the classical PCP theorem---and prove that it amplifies the combinatorial gap. The construction develops a new framework for reasoning about gap amplification in terms of fault-tolerant distributed computation, along with new tools in secure multiparty computation and high-dimensional expanders.

•Jan 1, 2026•0 citations

Fault-tolerant interfaces for quantum LDPC codes

Matthias Christandl, Omar Fawzi, Ashutosh Goswami

The preparation of a quantum state using a noisy quantum computer (gate noise strength $δ$) will necessarily affect an O($δ$)-fraction of the qubits, no matter which protocol is used. Here, we show that fault-tolerant quantum state preparation can be achieved with constant space overhead improving on previous constructions requiring polylogarithmic overhead. To achieve this, we add to the toolbox of fault-tolerant schemes for circuits with quantum input and output. More specifically, we construct fault-tolerant interfaces that decrease the level of protection for quantum low-density parity-check (LDPC) codes. When information is encoded in multiple code blocks, our interfaces have constant space overhead. In our decoder construction that change the level of protection by an arbitrary amount, we circumvent bottlenecks to error pileup and overhead by gradual lowering of the level of encoding at the same time as we increase the number of blocks on which decoding is carried out simultaneously.

quant-pharXiv:2602.16948•Feb 20, 2026•0 citations

Polylog-time- and constant-space-overhead fault-tolerant quantum computation with quantum low-density parity-check codes

Shiro Tamiya, Masato Koashi, Hayata Yamasaki

A major challenge in fault-tolerant quantum computation (FTQC) is to reduce both space overhead -- the large number of physical qubits per logical qubit -- and time overhead -- the long physical gate sequences per logical gate. We prove that a protocol using non-vanishing-rate quantum low-density parity-check (LDPC) codes, combined with concatenated Steane codes, achieves constant space overhead and polylogarithmic time overhead, even when accounting for non-zero classical computation time. This protocol offers an improvement over existing constant-space-overhead protocols, which have polynomial time overhead using quantum LDPC codes and quasi-polylogarithmic time overhead using concatenated quantum Hamming codes. To ensure the completeness of this proof, we develop a technique called partial circuit reduction, which enables error analysis for the entire fault-tolerant circuit by examining smaller parts composed of a few gadgets. With this technique, we resolve a previously unaddressed logical gap in the existing arguments and complete the proof of the threshold theorem for the constant-space-overhead protocol with quantum LDPC codes. Our work highlights that the quantum-LDPC-code approach can realize FTQC with a negligibly small slowdown and a bounded overhead of physical qubits, similar to the code-concatenation approach, underscoring the importance of a comprehensive comparison of the future realizability of these two approaches.

arXiv:2411.03683•Nov 6, 2024•0 citations

Non-local fault-tolerance and quasiprobabilty models in quantum computing

Lawrence Z. Cohen

In this thesis we explore two topics related to quantum computing. In the first part of this thesis we explore how geometrically non-local quantum low-density parity-check (LDPC) codes can be utilised to enable fault-tolerant quantum computing with reduced physical overheads. We design a scheme to implement any Clifford gate via measurements of logical Pauli operators on quantum LDPC codes. When supplemented with magic states this is sufficient for performing universal quantum computing. We prove that our scheme preserves the distance of the code and show that low overheads are maintained. We then show how we can construct quantum LDPC codes that are tailored to account for biased depolarising noise. We conduct numerical simulations using the BP-OSD decoder, and showing favorable scaling compared to non-tailored quantum LDPC codes and tailored surface codes. Overall, we provide evidence that fault-tolerant quantum computing with LDPC codes has the potential to reduce overheads significantly when compared to conventional surface code schemes. In the second part of this thesis we explore quasiprobability representations for quantum computation in the magic state model. We define a new model based on generalized Jordan-Wigner transformations that has a close connection to the probability representation of universal quantum computation based on the $\Lambda$ polytopes. It leads to an efficient classical simulation algorithm for magic state quantum circuits for which the input state is positively represented, and it outperforms previous representations in terms of the states that can be positively represented. For each number of qubits the model defines a polytope contained in the $\Lambda$ polytope with some shared vertices. We characterise these vertices, which by polar duality also allows us to characterise new facets of the stabiliser polytope.

•Jan 1, 2024•0 citations

Accelerating Fault-Tolerant Quantum Computation with Good Quantum Low-Density Parity-Check Codes

Guo Zhang, Yuanye Zhu, Ying Li

We propose a fault-tolerant quantum computation scheme that is broadly applicable to quantum low-density parity-check (qLDPC) codes. The scheme achieves constant qubit overhead and a time overhead of O ( d a + o ( 1 ) ) for any [ [ n , k , d ] ] qLDPC code with constant encoding rate and distance d = Ω ( n 1 / a ) . For good qLDPC codes, the time overhead is minimized and reaches O ( d 1 + o ( 1 ) ) . In contrast, code surgery based on gauging measurement and brute-force branching requires a time overhead of O ( d w 1 + o ( 1 ) ) , where d ≤ w ≤ n . Thus, our scheme is asymptotically faster for all codes with a < 2 . This speedup is achieved by developing techniques that enable parallelized code surgery under constant qubit overhead and leverage classical locally testable codes for efficient resource state preparation. These results establish a new paradigm for accelerating fault-tolerant quantum computation on qLDPC codes, while maintaining low overhead and broad applicability.

arXiv:2510.19442•PRX Quantum•Jun 3, 2026•0 citations
Quantum computing offers promising potential for faster computation compared to classical computing, with the advantage of improved scaling as the problem size increases.Many fast quantum algorithms have been developed to solve specific problems using quantum computation, and they are expected to be applied to a wide range of fields, including quantum chemistry, condensed matter physics, and machine learning.However, the high cost of realizing physical systems to perform quantum computations makes resource-efficient implementation methods indispensable.In the first part of this thesis, we study the resource-efficient design of a fault-tolerant protocol based on quantum low-density parity-check (LDPC) codes.Scalable quantum computation to achieve the speed-ups over classical computation requires fault tolerance due to the vulnerability of quantum systems to noise.Fault-tolerant quantum computation (FTQC) expenses significant space and time overheads to achieve fault-tolerant quantum circuits from the original circuits intended to simulate.An FTQC protocol based on quantum LDPC codes has the attractive advantage of constant-space overhead, but has the disadvantage of requiring a long polynomial-time overhead.In this thesis, we present a polylogarithmic time overhead FTQC protocol based on quantum LDPC code, which is exponentially time efficient compared to conventional protocols while maintaining the advantage of the constant space overhead.This overhead is enjoyed even if the non-zero classical computation performing the decoding algorithms is considered.The second part of this thesis investigates the resource-efficient design of variational quantum algorithms (VQAs).The VQAs are a heuristic algorithm with promising applications in various fields.The VQAs can be performed by minimizing task-specific cost functions, typically defined as the expectation values of observables.However, it is known that the execution of variational quantum algorithms requires numerous quantum measurements, and their reduction is a significant challenge in algorithm implementation.In the first study of this part, we propose a new algorithm for calculating nonadiabatic couplings (NACs), which are important quantities in simulating molecular
Abstract Scalable realization of quantum computing to attain substantial speedups over classical computing requires fault tolerance. Conventionally, protocols for fault-tolerant quantum computation (FTQC) demand excessive space overhead of physical qubits per logical qubit. A more recent protocol to achieve constant-space-overhead FTQC using quantum low-density parity-check (LDPC) codes thus attracts considerable attention but suffers from another drawback: it incurs polynomially long time overhead. To address these problems, we here introduce an alternative approach using a concatenation of multiple small-size quantum codes for the constant-space-overhead FTQC rather than a single large-size quantum LDPC code. We develop techniques for concatenating different quantum Hamming codes with growing sizes. As a result, we construct a low-overhead protocol to achieve constant space overhead and only quasi-polylogarithmic time overhead simultaneously. Our protocol accomplishes FTQC even if a decoder has non-constant runtime, unlike the existing constant-space-overhead protocol. These results establish a foundation for FTQC realizing a large class of quantum speedups within feasibly bounded space overhead yet negligibly short time overhead. This achievement opens a promising avenue for the low-overhead FTQC based on code concatenation.
The theory of fault tolerance is a cornerstone of computing and many modern technologies. With the development of quantum science and engineering, fault tolerance has become increasingly important, as quantum systems are intrinsically susceptible to noise. This thesis presents several advances in quantum fault tolerance and develops new connections between fault tolerance and quantum complexity theory. In Part I, we construct a fault-tolerant quantum computation scheme with constant space overhead and near-logarithmic time overhead. This is the lowest overhead achieved to date and and provides the first rigorous proof that fault tolerance based on quantum low-density parity-check (qLDPC) codes can achieve better asymptotic spacetime overhead than conventional schemes. The construction relies on locally testable qLDPC codes and new quantum state distillation algorithms with improved spacetime overhead. Additionally, a variant of these algorithms yields the first magic state distillation algorithm with constant space overhead. In Part II, we make progress on the quantum probabilistically checkable proofs (PCP) conjecture by using ideas from fault tolerance. We introduce a new circuit-to-Hamiltonian mapping that allows Hamiltonians to inherit the fault tolerance properties of quantum circuits. Using this new mapping, we construct the first known template for quantum locality-preserving gap amplification---the quantum analogue of a central ingredient in the classical PCP theorem---and prove that it amplifies the combinatorial gap. The construction develops a new framework for reasoning about gap amplification in terms of fault-tolerant distributed computation, along with new tools in secure multiparty computation and high-dimensional expanders.
The preparation of a quantum state using a noisy quantum computer (gate noise strength δδδ) will necessarily affect an O(δδδ)-fraction of the qubits, no matter which protocol is used. Here, we show that fault-tolerant quantum state preparation can be achieved with constant space overhead improving on previous constructions requiring polylogarithmic overhead. To achieve this, we add to the toolbox of fault-tolerant schemes for circuits with quantum input and output. More specifically, we construct fault-tolerant interfaces that decrease the level of protection for quantum low-density parity-check (LDPC) codes. When information is encoded in multiple code blocks, our interfaces have constant space overhead. In our decoder construction that change the level of protection by an arbitrary amount, we circumvent bottlenecks to error pileup and overhead by gradual lowering of the level of encoding at the same time as we increase the number of blocks on which decoding is carried out simultaneously.
A major challenge in fault-tolerant quantum computation (FTQC) is to reduce both space overhead -- the large number of physical qubits per logical qubit -- and time overhead -- the long physical gate sequences per logical gate. We prove that a protocol using non-vanishing-rate quantum low-density parity-check (LDPC) codes, combined with concatenated Steane codes, achieves constant space overhead and polylogarithmic time overhead, even when accounting for non-zero classical computation time. This protocol offers an improvement over existing constant-space-overhead protocols, which have polynomial time overhead using quantum LDPC codes and quasi-polylogarithmic time overhead using concatenated quantum Hamming codes. To ensure the completeness of this proof, we develop a technique called partial circuit reduction, which enables error analysis for the entire fault-tolerant circuit by examining smaller parts composed of a few gadgets. With this technique, we resolve a previously unaddressed logical gap in the existing arguments and complete the proof of the threshold theorem for the constant-space-overhead protocol with quantum LDPC codes. Our work highlights that the quantum-LDPC-code approach can realize FTQC with a negligibly small slowdown and a bounded overhead of physical qubits, similar to the code-concatenation approach, underscoring the importance of a comprehensive comparison of the future realizability of these two approaches.
In this thesis we explore two topics related to quantum computing. In the first part of this thesis we explore how geometrically non-local quantum low-density parity-check (LDPC) codes can be utilised to enable fault-tolerant quantum computing with reduced physical overheads. We design a scheme to implement any Clifford gate via measurements of logical Pauli operators on quantum LDPC codes. When supplemented with magic states this is sufficient for performing universal quantum computing. We prove that our scheme preserves the distance of the code and show that low overheads are maintained. We then show how we can construct quantum LDPC codes that are tailored to account for biased depolarising noise. We conduct numerical simulations using the BP-OSD decoder, and showing favorable scaling compared to non-tailored quantum LDPC codes and tailored surface codes. Overall, we provide evidence that fault-tolerant quantum computing with LDPC codes has the potential to reduce overheads significantly when compared to conventional surface code schemes. In the second part of this thesis we explore quasiprobability representations for quantum computation in the magic state model. We define a new model based on generalized Jordan-Wigner transformations that has a close connection to the probability representation of universal quantum computation based on the Λ\LambdaΛ polytopes. It leads to an efficient classical simulation algorithm for magic state quantum circuits for which the input state is positively represented, and it outperforms previous representations in terms of the states that can be positively represented. For each number of qubits the model defines a polytope contained in the Λ\LambdaΛ polytope with some shared vertices. We characterise these vertices, which by polar duality also allows us to characterise new facets of the stabiliser polytope.
We propose a fault-tolerant quantum computation scheme that is broadly applicable to quantum low-density parity-check (qLDPC) codes. The scheme achieves constant qubit overhead and a time overhead of O ( d a + o ( 1 ) ) for any [ [ n , k , d ] ] qLDPC code with constant encoding rate and distance d = Ω ( n 1 / a ) . For good qLDPC codes, the time overhead is minimized and reaches O ( d 1 + o ( 1 ) ) . In contrast, code surgery based on gauging measurement and brute-force branching requires a time overhead of O ( d w 1 + o ( 1 ) ) , where d ≤ w ≤ n . Thus, our scheme is asymptotically faster for all codes with a < 2 . This speedup is achieved by developing techniques that enable parallelized code surgery under constant qubit overhead and leverage classical locally testable codes for efficient resource state preparation. These results establish a new paradigm for accelerating fault-tolerant quantum computation on qLDPC codes, while maintaining low overhead and broad applicability.