• Rapid Communication

Hardness of classically sampling the one-clean-qubit model with constant total variation distance error

Tomoyuki Morimae
Phys. Rev. A 96, 040302(R) – Published 5 October 2017

Abstract

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.

  • Received 3 June 2017

DOI:https://doi.org/10.1103/PhysRevA.96.040302

©2017 American Physical Society

Physics Subject Headings (PhySH)

  1. Research Areas
Quantum Information, Science & Technology

Authors & Affiliations

Tomoyuki Morimae*

  • Department of Computer Science, Gunma University, 1-5-1 Tenjincho, Kiryu, Gunma 376-0052, Japan

  • *morimae@gunma-u.ac.jp

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 96, Iss. 4 — October 2017

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×