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

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 sub-universal quantum computing models such as the IQP 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 anti-concentration 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.

9 pages

References in corpus (1)

• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

Cited by in corpus (33)

• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Variational Quantum Linear Solver
• Computational advantage of quantum random sampling
• Theory of quantum system certification: a tutorial
• Variational Quantum Fidelity Estimation
• Random quantum circuits anti-concentrate in log depth
• Verification of Many-Qubit States
• Computational power of one- and two-dimensional dual-unitary quantum circuits
• Anticoncentration theorems for schemes showing a quantum speedup
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• From estimation of quantum probabilities to simulation of quantum circuits
• Towards quantum advantage via topological data analysis
• Sample complexity of device-independently certified "quantum supremacy"
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Quantum Algorithm for Fidelity Estimation
• Quantum Mixed State Compiling
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Nonadaptive fault-tolerant verification of quantum supremacy with noise
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Complexity Classification of Conjugated Clifford Circuits
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Quantum advantage from energy measurements of many-body quantum systems
• Boson Sampling for Generalized Bosons
• Learning from physics experiments, with quantum computers: Applications in muon spectroscopy
• Additive-error fine-grained quantum supremacy
• The one clean qubit model without entanglement is classically simulable
• Impossibility of blind quantum sampling for classical client
• Pinned QMA: The power of fixing a few qubits in proofs
• Resource-efficient quantum algorithm for linear systems of equations
• Sampling of globally depolarized random quantum circuit
• Fine-grained quantum computational supremacy
• Cryptographic Characterization of Quantum Advantage