4.6 Article

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

Journal

PHYSICAL REVIEW A
Volume 96, Issue 4, Pages -

Publisher

AMER PHYSICAL SOC
DOI: 10.1103/PhysRevA.96.040302

Keywords

-

Funding

  1. JST ACT-I [JPMJPR16UP]
  2. MEXT Japan [15H00850]
  3. JSPS [26730003, 17K12637]
  4. Grants-in-Aid for Scientific Research [26730003, 17K12637, 15H00850] Funding Source: KAKEN

Ask authors/readers for more resources

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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available