For two unknown mixed quantum states $\rho $ and $\sigma $ in an $N$ -dimensional Hilbert space, computing their fidelity $F(\rho,\sigma)$ is a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem in ${\mathrm{ poly}}(\log (N), r, 1/\varepsilon)$ time, where $r$ is the lower rank of $\rho $ and $\sigma $ , and $\varepsilon $ is the desired precision, provided that the purifications of $\rho $ and $\sigma $ are prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial in $N$ .
31 March 2023 in IEEE Transactions on Information Theory
Estimating the unitarity of an unknown quantum channel E provides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that use O (ϵ –2 ) and O ( √ d ∙ϵ –2 ) calls to E with coherent and incoherent accesses, respectively, where d is the dimension of the system that E acts on and ϵ is the required precision. We further show that both the d -dependence and ϵ-dependence of our algorithms are optimal. As part of our results, we settle the query complexity of the distinguishing problem for depolarizing and unitary channels with incoherent access by giving a matching lower bound Ω( √ d ), improving the prior best lower bound Ω( ∛ d ) by Aharonov et al. (Nat. Commun. 2022) and Chen et al. (FOCS 2021).
Quantum computers have advanced rapidly in qubit count and gate fidelity. However, large-scale fault-tolerant quantum computing still relies on quantum error correction code (QECC) to suppress noise. Manually or experimentally verifying the fault-tolerance property of complex QECC implementation is impractical due to the vast error combinations. This paper formalizes the fault-tolerance of QECC implementations within the language of quantum programs. By incorporating the techniques of quantum symbolic execution, we provide an automatic verification tool for quantum fault-tolerance. We evaluate and demonstrate the effectiveness of our tool on a universal set of logical operations across different QECCs.
18 September 2024 in ACM Transactions on Design Automation of Electronic Systems
Quantum circuit testing is essential for detecting potential faults in realistic quantum devices, while the testing process itself also suffers from the inexactness and unreliability of quantum operations. This article alleviates the issue by proposing a novel framework of automatic test pattern generation (ATPG) for robust testing of logical quantum circuits. We introduce the stabilizer projector decomposition (SPD) for representing the quantum test pattern and construct the test application (i.e., state preparation and measurement) using Clifford-only circuits, which are rather robust and efficient as evidenced in the fault-tolerant quantum computation. However, it is generally hard to generate SPDs due to the exponentially growing number of the stabilizer projectors. To circumvent this difficulty, we develop an SPD generation algorithm, as well as several acceleration techniques that can exploit both locality and sparsity in generating SPDs. The effectiveness of our algorithms are validated by (1) theoretical guarantees under reasonable conditions and (2) experimental results on commonly used benchmark circuits, such as Quantum Fourier Transform (QFT), Quantum Volume (QV), and Bernstein-Vazirani (BV) in IBM Qiskit.
Quantum error correction (QEC) is essential for scalable quantum computing, yet repeated syndrome-measurement cycles dominate its spacetime and hardware cost. Although stabilizers commute and admit many valid execution orders, different schedules induce distinct error-propagation paths under realistic noise, leading to large variations in logical error rate. Outside of surface codes, effective syndrome-measurement scheduling remains largely unexplored. We present AlphaSyndrome, an automated synthesis framework for scheduling syndrome-measurement circuits in general commuting-stabilizer codes under minimal assumptions: mutually commuting stabilizers and a heuristic decoder. AlphaSyndrome formulates scheduling as an optimization problem that shapes error propagation to (i) avoid patterns close to logical operators and (ii) remain within the decoder's correctable region. The framework uses Monte Carlo Tree Search (MCTS) to explore ordering and parallelism, guided by code structure and decoder feedback. Across diverse code families, sizes, and decoders, AlphaSyndrome reduces logical error rates by 80.6% on average (up to 96.2%) relative to depth-optimal baselines, matches Google's hand-crafted surface-code schedules, and outperforms IBM's schedule for the Bivariate Bicycle code.
4 June 2026 in IEEE Transactions on Information Theory
We consider a fundamental task in quantum information theory, estimating the values of tr(Oρ), tr(Oρ2), . . . , tr(Oρk) for an observable O and a quantum state ρ. We show that Θ(k) samples of ρ are sufficient and necessary to simultaneously estimate all the k values. This means that estimating all the k values is almost as easy as estimating only one of them, tr(Oρk). As an application, our approach advances the sample complexity of entanglement spectroscopy and the virtual cooling for quantum many-body systems. Moreover, we extend our approach to estimating general functionals by polynomial approximation.