2017/04/12 by Tomoyuki Morimae · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Astrophysics #Computer science #Constant (computer programming) #Mathematics #Physics #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Sampling (signal processing) #Statistics #Telecommunications #Variation (astronomy) #cs.CC #quant-ph
paper · pdf · doi:10.1103/physreva.96.040302
published as Phys. Rev. A 96, 040302(R) (2017) · 9 pages
arxiv created 2017/04/12 · openalex publication_date 2017/10/05 · arxiv updated 2017/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The one-clean-qubit model (or the DQC1 model) is a restricted model of quantum computing where only a single input qubit is pure and all other input qubits are maximally mixed. In spite of the severe restriction, the model can solve several problems (such as calculating Jones polynomials) whose classical efficient solutions are not known. Furthermore, it was shown that if the output probability distribution of the one-clean-qubit model can be classically efficiently sampled with a constant multiplicative error, then the polynomial hierarchy collapses to the second level. Is it possible to improve the multiplicative error hardness result to a constant total variation distance error one like other subuniversal quantum computing models such as the IQP (Instantaneous Quantum Polynomial time) model, the boson sampling model, and the Fourier sampling model? In this paper we show that it is indeed possible if we accept a modified version of the average case hardness conjecture. Interestingly, the anticoncentration lemma can be easily shown by using the special property of the one-clean-qubit model that each output probability is so small that no concentration occurs.