Efficient Quantum State Identity Testing
Abstract
We study the following quantum state identity problem: given access to copies of n unknown pure quantum states, the goal is to determine whether every pair has fidelity at least 1−ε or some pair has fidelity at most ε. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter ε∈(0,1/4), we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes O(log(n/δ)log(2/δ)) copies of each input state to succeed with probability at least 1−δ. The second uses the Schur transform to reduce the sample complexity to O(log(n/δ)), through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of Ω(log(n/δ)) for any quantum algorithm with failure probability at most δ≤ 1/2−c, for any constant c>0, establishing that the second algorithm achieves the optimal dependence on both n and δ for fixed ε.
Related
- Counterdiabatic quantum optimization for efficient state preparation in the Schwinger model
- Efficient quantum state tomography with two complementary projective measurements
- Efficient Quantum Algorithm for Mixed-State Quantum Geometry
- Variational Perturbation Theory in Open Quantum Systems for Efficient Steady State Computation
- Fault-Tolerant Logical Operations and Efficient State Preparation in Modular Quantum Architectures with Noisy Interfaces
BibTeX
@misc{hung2026efficient,
title = {{Efficient Quantum State Identity Testing}},
author = {Shih-Han Hung and Ming-Hsien Tsai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04597},
eprint = {2610.04597},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04597},
}
RIS
TY - UNPB
TI - Efficient Quantum State Identity Testing
AU - Shih-Han Hung
AU - Ming-Hsien Tsai
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04597
UR - https://arxiv.org/abs/2610.04597
AB - We study the following quantum state identity problem: given access to copies of n unknown pure quantum states, the goal is to determine whether every pair has fidelity at least 1−ε or some pair has fidelity at most ε. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter ε∈(0,1/4), we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes O(log(n/δ)log(2/δ)) copies of each input state to succeed with probability at least 1−δ. The second uses the Schur transform to reduce the sample complexity to O(log(n/δ)), through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of Ω(log(n/δ)) for any quantum algorithm with failure probability at most δ≤ 1/2−c, for any constant c>0, establishing that the second algorithm achieves the optimal dependence on both n and δ for fixed ε.
ER -