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

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

Lawrence Z. Cohen

Published Jan 1, 2024• 0 citations
OpenAlex

Abstract

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.

Related papers

Architectures for fault-tolerant quantum computation

Joe O’Gorman

Quantum computing has enormous potential, but this can only be realised if quantum errors can be controlled sufficiently to allow quantum algorithms to be completed reliably. However, quantum-error-corrected logical quantum bits (qubits) which can be said to have achieved meaningful error suppression have not yet been demonstrated. This thesis reports research on several topics related to the challenge of designing fault-tolerant quantum computers. The first topic is a proposal for achieving large-scale error correction with the surface code in a silicon donor based quantum computing architecture. This proposal relaxes some of the stringent requirements in donor placement precision set by previous ideas from the single atom level to the order of 10 nm in some regimes. This is shown by means of numerical simulation of the surface code threshold. The second topic then follows, it is the development of a method for benchmarking and assessing the performance of small error correcting codes in few-qubit systems, introducing a metric called 'integrity' - closely linked to the trace distance -- and a proposal for experiments to demonstrate various stepping stones on the way to 'strictly superior' quantum error correction. Most quantum error correcting codes, including the surface code, do not allow for fault-tolerant universal computation without the addition of extra gadgets. One method of achieving universality is through a process of distilling and then consuming high quality 'magic states'. This process adds additional overhead to quantum computation over and above that incurred by the use of the base level quantum error correction. The latter parts of this thesis report an investigation into how many physical qubits are needed in a `magic state factory' within a surface code quantum computer and introduce a number of techniques to reduce the overhead of leading magic state techniques. It is found that universal quantum computing is achievable with ∼ 16 million qubits if error rates across a device are kept below 10-4. In addition, the thesis introduces improved methods of achieving magic state distillation for unconventional magic states that allow for logical small angle rotations, and show that this can be more efficient than synthesising these operations from the gates provided by traditional magic states.

•Jan 1, 2017•0 citations

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

Shiro Tamiya

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

•Mar 21, 2024•0 citations

Magic Quantum Code Surgery

Kathleen Chang, Anasuya Lyons, Yuanjie Ren +5 more

Non-Clifford operations required for universal quantum computation can be implemented by measuring logical Clifford operators. We present a generalized framework to fault-tolerantly measure transversal Clifford logical operators in quantum low-density parity check (QLDPC) codes. Our protocol takes any QLDPC code and deforms the code across additional ancillary qubits such that a product of stabilizers measures the desired logical Clifford operator. We prove that the deformed, Clifford-stabilized code remains LDPC and that its distance is preserved up to a constant factor independent of the number of physical qubits. We further prove that the Clifford measurement has a fault distance against data qubit and measurement errors that grows linearly with the distance of the original code. We apply our methods to implement logical non-Clifford gates in algorithmically relevant subroutines and to prepare magic states in quantum stabilizer codes.

quant-pharXiv:2610.03920•Oct 6, 2026•0 citations

Low-overhead fault-tolerant quantum computing using long-range connectivity

Lawrence Z. Cohen, Isaac H. Kim, Stephen D. Bartlett +1 more

Vast numbers of qubits will be needed for large-scale quantum computing because of the overheads associated with error correction. We present a scheme for low-overhead fault-tolerant quantum computation based on quantum low-density parity-check (LDPC) codes, where long-range interactions enable many logical qubits to be encoded with a modest number of physical qubits. In our approach, logic gates operate via logical Pauli measurements that preserve both the protection of the LDPC codes and the low overheads in terms of the required number of additional qubits. Compared with surface codes with the same code distance, we estimate order-of-magnitude improvements in the overheads for processing around 100 logical qubits using this approach. Given the high thresholds demonstrated by LDPC codes, our estimates suggest that fault-tolerant quantum computation at this scale may be achievable with a few thousand physical qubits at comparable error rates to what is needed for current approaches.

arXiv:2110.10794•Science Advances•May 20, 2022•98 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

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
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.
Quantum computing has enormous potential, but this can only be realised if quantum errors can be controlled sufficiently to allow quantum algorithms to be completed reliably. However, quantum-error-corrected logical quantum bits (qubits) which can be said to have achieved meaningful error suppression have not yet been demonstrated. This thesis reports research on several topics related to the challenge of designing fault-tolerant quantum computers. The first topic is a proposal for achieving large-scale error correction with the surface code in a silicon donor based quantum computing architecture. This proposal relaxes some of the stringent requirements in donor placement precision set by previous ideas from the single atom level to the order of 10 nm in some regimes. This is shown by means of numerical simulation of the surface code threshold. The second topic then follows, it is the development of a method for benchmarking and assessing the performance of small error correcting codes in few-qubit systems, introducing a metric called 'integrity' - closely linked to the trace distance -- and a proposal for experiments to demonstrate various stepping stones on the way to 'strictly superior' quantum error correction. Most quantum error correcting codes, including the surface code, do not allow for fault-tolerant universal computation without the addition of extra gadgets. One method of achieving universality is through a process of distilling and then consuming high quality 'magic states'. This process adds additional overhead to quantum computation over and above that incurred by the use of the base level quantum error correction. The latter parts of this thesis report an investigation into how many physical qubits are needed in a `magic state factory' within a surface code quantum computer and introduce a number of techniques to reduce the overhead of leading magic state techniques. It is found that universal quantum computing is achievable with ∼ 16 million qubits if error rates across a device are kept below 10-4. In addition, the thesis introduces improved methods of achieving magic state distillation for unconventional magic states that allow for logical small angle rotations, and show that this can be more efficient than synthesising these operations from the gates provided by traditional magic states.
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
Non-Clifford operations required for universal quantum computation can be implemented by measuring logical Clifford operators. We present a generalized framework to fault-tolerantly measure transversal Clifford logical operators in quantum low-density parity check (QLDPC) codes. Our protocol takes any QLDPC code and deforms the code across additional ancillary qubits such that a product of stabilizers measures the desired logical Clifford operator. We prove that the deformed, Clifford-stabilized code remains LDPC and that its distance is preserved up to a constant factor independent of the number of physical qubits. We further prove that the Clifford measurement has a fault distance against data qubit and measurement errors that grows linearly with the distance of the original code. We apply our methods to implement logical non-Clifford gates in algorithmically relevant subroutines and to prepare magic states in quantum stabilizer codes.
Vast numbers of qubits will be needed for large-scale quantum computing because of the overheads associated with error correction. We present a scheme for low-overhead fault-tolerant quantum computation based on quantum low-density parity-check (LDPC) codes, where long-range interactions enable many logical qubits to be encoded with a modest number of physical qubits. In our approach, logic gates operate via logical Pauli measurements that preserve both the protection of the LDPC codes and the low overheads in terms of the required number of additional qubits. Compared with surface codes with the same code distance, we estimate order-of-magnitude improvements in the overheads for processing around 100 logical qubits using this approach. Given the high thresholds demonstrated by LDPC codes, our estimates suggest that fault-tolerant quantum computation at this scale may be achievable with a few thousand physical qubits at comparable error rates to what is needed for current approaches.
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.
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.