Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
arXiv:1711.10605 · doi:10.22331/q-2018-11-15-106
Abstract
We introduce a simple sub-universal quantum computing model, which we call the Hadamard-classical circuit with one-qubit (HC1Q) model. It consists of a classical reversible circuit sandwiched by two layers of Hadamard gates, and therefore it is in the second level of the Fourier hierarchy. We show that output probability distributions of the HC1Q model cannot be classically efficiently sampled within a multiplicative error unless the polynomial-time hierarchy collapses to the second level. The proof technique is different from those used for previous sub-universal models, such as IQP, Boson Sampling, and DQC1, and therefore the technique itself might be useful for finding other sub-universal models that are hard to classically simulate. We also study the classical verification of quantum computing in the second level of the Fourier hierarchy. To this end, we define a promise problem, which we call the probability distribution distinguishability with maximum norm (PDD-Max). It is a promise problem to decide whether output probability distributions of two quantum circuits are far apart or close. We show that PDD-Max is BQP-complete, but if the two circuits are restricted to some types in the second level of the Fourier hierarchy, such as the HC1Q model or the IQP model, PDD-Max has a Merlin-Arthur system with quantum polynomial-time Merlin and classical probabilistic polynomial-time Arthur.
arXiv comment30 pages, 4 figures
References in corpus (20)
- Elementary gates for quantum computation
- 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
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Unconditionally verifiable blind computation
- Verifiable measurement-only blind quantum computing with stabilizer testing
- Verification of quantum computation: An overview of existing approaches
- On the hardness of classically simulating the one clean qubit model
- Post hoc verification with a single prover
- Post hoc verification of quantum computation
- Interactive proofs for BQP via self-tested graph states
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- How to Verify a Quantum Computation
- Hardness of classically sampling one clean qubit model with constant total variation distance error
- Quantum proofs can be verified using only single qubit measurements
- Power of Quantum Computation with Few Clean Qubits
- Quantum and Classical Tradeoffs
- Classical verification of quantum circuits containing few basis changes
- Complexity Classification of Conjugated Clifford Circuits
Cited by in corpus (9)
- How many qubits are needed for quantum computational supremacy?
- Efficient classical simulation of Clifford circuits with nonstabilizer input states
- Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states
- Verifying commuting quantum computations via fidelity estimation of weighted graph states
- Sumcheck-based delegation of quantum computing to rational server
- On the role of coherence for quantum computational advantage
- Additive-error fine-grained quantum supremacy
- Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
- Hardness of efficiently generating ground states in postselected quantum computation