Hardness of classically sampling one clean qubit model with constant total variation distance error
arXiv:1704.03640 · doi:10.1103/PhysRevA.96.040302
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.
arXiv comment9 pages
References in corpus (10)
- On the Power of One Bit of Quantum Information
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- On the hardness of classically simulating the one clean qubit model
- Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect
- Quantum Commuting Circuits and Complexity of Ising Partition Functions
- Experimental approximation of the Jones polynomial with DQC1
- Testing integrability with a single bit of quantum information
- Power of Quantum Computation with Few Clean Qubits
- Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit
Cited by in corpus (35)
- 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
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- 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 Algorithm for Fidelity Estimation
- Quantum advantage of unitary Clifford circuits with magic state inputs
- 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
- Power of Uninitialized Qubits in Shallow Quantum 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
- Sampling of globally depolarized random quantum circuit
- Pinned QMA: The power of fixing a few qubits in proofs
- Resource-efficient quantum algorithm for linear systems of equations
- Impossibility of blind quantum sampling for classical client
- Fine-grained quantum computational supremacy
- Cryptographic Characterization of Quantum Advantage