Quantum Computer Error Checks Now Need Just One Sample Per Qubit

Researchers are continually seeking methods to accurately and efficiently assess the performance of quantum computations, a critical step in developing reliable quantum technologies. Guedong Park from NextQuantum Innovation Research Center and Seoul National University, alongside Jaekwon Chang and Yosep Kim from Korea University, and Yong Siah Teo et al., present a novel fidelity estimation algorithm that dramatically reduces the resources needed for this assessment. Their work addresses a significant limitation of direct fidelity estimation, which typically demands an exponentially large number of samples, particularly when evaluating complex quantum states. By introducing a technique called ‘phase stripping’ and converting complex gate requirements into classical post-processing, the team demonstrates fidelity estimation using substantially fewer samples, scaling to just one for certain target states, and with a single fan-out gate, paving the way for more feasible and noise-resilient quantum algorithms.

This breakthrough addresses a critical limitation of current methods, which often require exponentially increasing resources as the complexity of the quantum state increases.

The research introduces a technique called ‘phase stripping’ that significantly lowers the computational cost of verifying quantum states, particularly those with complex phase structures. By converting complex diagonal gate requirements into nonlinear classical post-processing of Pauli measurements, the algorithm achieves substantial efficiency gains.
This work demonstrates that fidelity estimation for pure states resembling phase states can be accomplished using a number of sampling copies that scales polynomially with the number of qubits, denoted as O(poly(n)). This represents a significant improvement over conventional direct fidelity estimation (DFE), which typically demands exponentially many samples.

As the target state approaches a pure phase state, the sampling complexity is reduced to a constant, O(1). The core innovation lies in the phase stripping process, which effectively diminishes the ‘magic’ inherent in the target state, thereby simplifying the fidelity calculation. Furthermore, researchers have proposed a nonlinear extension to the conventional DFE scheme, preserving the use of Pauli measurements while still guaranteeing a reduction in sampling requirements.
This is achieved through nonlinear post-processing, eliminating the need for complex gate resources. The algorithm relies on a single n-qubit fan-out gate, a readily available component in current experimental setups. This advancement promises to enable the development of more robust and efficient quantum algorithms by minimising the overhead associated with fidelity estimation.

The study highlights the importance of optimising the trade-off between sampling complexity and gate complexity in quantum computation. By focusing on reducing sampling overhead under restricted gate resources, this research contributes to clarifying the fundamental limits of this trade-off. Ultimately, this work aims to bridge the gap between the resources needed to understand complex physical properties and those required to generate them, paving the way for more powerful and practical quantum technologies.

Phase stripping and efficient fidelity assessment utilising classical post-processing

Direct fidelity estimation (DFE) typically demands exponentially many sampling copies to accurately assess fidelity with a target pure state. This research introduces a sample- and gate-efficient fidelity estimation algorithm designed for implementation on feasible quantum devices. The study demonstrates that fidelity estimation for pure states resembling phase states, which present challenges for sample-efficient DFE due to strong entanglement and magic, can be achieved using O(poly(n)) sampling copies and a single n-qubit fan-out gate.

A crucial innovation within this methodology is termed ‘phase stripping’, a process that substantially reduces the target-state magic. This phase stripping transforms the coefficients of the computational basis into their moduli, effectively diminishing the complexity of the state. Researchers then converted complex diagonal gate resources, initially required for a phase-stripping-adapted algorithm, into nonlinear classical post-processing of Pauli measurements.

This conversion ensures that only a single fan-out gate is necessary for the entire procedure. Furthermore, a nonlinear extension of the conventional DFE scheme was proposed, also leveraging nonlinear post-processing. This variant guarantees a reduction in sampling requirements compared to standard DFE, while maintaining Pauli measurements as the sole circuit resource.

The experimental setup relies on a Hadamard test circuit to estimate target fidelity, followed by the translation of complex controlled-diagonal operations into the aforementioned nonlinear classical post-processing. The sampling complexity, in certain cases, reaches O, representing a significant improvement over existing methods. The l-norm of the phase-stripped state of arbitrary phase states is unity, further contributing to the efficiency of the scheme.

Efficient fidelity estimation via phase stripping and nonlinear post-processing

Logical error rates of 2.9% per cycle have been attained through a newly developed sample- and gate-efficient fidelity estimation algorithm. This work addresses the limitations of direct fidelity estimation, which typically requires exponentially many sampling copies due to the complexity of target states.

The research demonstrates that fidelity estimation for pure states close to the structure of phase states, previously challenging due to strong entanglement, can be achieved using sampling copies with a single n-qubit fan-out gate. As the target state approaches a phase state, the sampling complexity reduces to O.

This significant improvement stems from a technique called phase stripping, which substantially reduces the target state’s norm. The complex diagonal gate resource required for phase-stripping adaptation has been converted into nonlinear classical post-processing of Pauli measurements, maintaining the need for only a single fan-out gate.

Furthermore, a nonlinear extension of the conventional direct fidelity estimation scheme has been proposed, guaranteeing sampling reduction while preserving Pauli measurements as the sole circuit resource. Specifically, the research establishes that for a fixed α between 0.5 and 1, the estimation variance depends on ∥ψ∥1/α 2−2α.

For random third-ordered hypergraph states, the l1-norm is approximately Θ(2n2), resulting in a sampling complexity for direct fidelity estimation of Θ(∥η∥21) ≃ O(2n). Phase stripping effectively reduces the l2−2α-norm of a given target state, particularly when magic is phase-dominated, generated by approximately O(2n) Clifford+T gates.

The study reveals that the proposed fan-out-based fidelity estimation scheme, termed α-FOFE, achieves a sampling complexity of O∥ψ∥1/α 2−2α ε2 log(Mδ−1f), where ε is the desired accuracy and δf is the failure probability. For M different target phase states sharing the same phase-stripped state, fidelity estimation can be completed with O(ε−2 log(Mδ−1f)) samples. This represents a substantial sample improvement as the target state converges towards a phase state, requiring neither prior block-diagonalization nor multi-copy measurements.

Phase stripping enables scalable quantum state fidelity estimation

Researchers have developed a sample- and gate-efficient algorithm for estimating the fidelity of quantum states, addressing a significant challenge in verifying the performance of quantum devices. Traditional direct fidelity estimation methods require an exponentially large number of copies of the target state, making them impractical for near-term quantum computers.

This new approach reduces the required sampling copies, particularly for states resembling phase structures, by employing a technique termed ‘phase stripping’. This reduction in complexity is achieved by transforming a computationally intensive diagonal gate resource into a nonlinear classical post-processing step, requiring only a single fan-out gate.

The core innovation lies in the ability to drastically reduce the target state’s complexity through phase stripping, enabling fidelity estimation with a sampling complexity that scales favourably with the system size. Furthermore, a variant of the scheme extends this reduction to conventional direct fidelity estimation, preserving the use of Pauli measurements as the primary circuit resource.

The algorithm’s efficiency is enhanced by utilising Bell sampling, a technique that allows for efficient l2-sampling when the target state’s unitary component is easily implemented. The total time complexity for calculating a marginal is demonstrated to be O(nχ4), with the overall time complexity reaching O(n2χ4).

Acknowledging limitations, the authors note that the efficiency of the algorithm relies on the target state possessing a specific structure, a diagonal gate combined with a relatively simple unitary transformation. Future research directions include extending the method to more general target states and exploring its application in establishing noise-resilient quantum algorithms. Ultimately, this work contributes to reducing the resource overhead associated with understanding complex quantum properties, potentially bridging the gap between the resources needed for analysis and those required for their physical realisation.