Verifying commuting quantum computations via fidelity estimation of weighted graph states
arXiv:1902.03369 · doi:10.1088/1367-2630/ab3d88
Abstract
The instantaneous quantum polynomial time model (or the IQP model) is one of promising models to demonstrate a quantum computational advantage over classical computers. If the IQP model can be efficiently simulated by a classical computer, an unlikely consequence in computer science can be obtained (under some unproven conjectures). In order to experimentally demonstrate the advantage using medium or large-scale IQP circuits, it is inevitable to efficiently verify whether the constructed IQP circuits faithfully work. There exists two types of IQP models, each of which is the sampling on hypergraph states or weighted graph states. For the first-type IQP model, polynomial-time verification protocols have already been proposed. In this paper, we propose verification protocols for the second-type IQP model. To this end, we propose polynomial-time fidelity estimation protocols of weighted graph states for each of the following four situations where a verifier can (i) choose any measurement basis and perform adaptive measurements, (ii) only choose restricted measurement bases and perform adaptive measurements, (iii) choose any measurement basis and only perform non-adaptive measurements, and (iv) only choose restricted measurement bases and only perform non-adaptive measurements. In all of our verification protocols, the verifier's quantum operations are only single-qubit measurements. Since we assume no i.i.d. property on quantum states, our protocols work in any situation.
References in corpus (34)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum Simulation
- Persistent entanglement in arrays of interacting particles
- Measurement-based quantum computation with cluster states
- Experimental quantum computing without entanglement
- Quantum Computational Supremacy
- Experimental Boson Sampling
- Photonic Boson Sampling in a Tunable Circuit
- Topological fault-tolerance in cluster state quantum computation
- 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion
- A fault-tolerant one-way quantum computer
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Experimental Scattershot Boson Sampling
- All Pure Bipartite Entangled States can be Self-Tested
- Verifiable measurement-only blind quantum computing with stabilizer testing
- Quantum Hypergraph States
- Instantaneous Quantum Computation
- Verification of Many-Qubit States
- Robust self testing of the 3-qubit state
- Efficient Verification of Hypergraph States
- Direct certification of a class of quantum simulations
- Trading inverses for an irrep in the Solovay-Kitaev theorem
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- Self-guaranteed measurement-based quantum computation
- Verifiable fault-tolerance in measurement-based quantum computation
- Hardness of classically sampling one clean qubit model with constant total variation distance error
- Sample complexity of device-independently certified "quantum supremacy"
- Universal MBQC with generalised parity-phase interactions and Pauli measurements
- Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
- Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
- Complexity Classification of Conjugated Clifford Circuits
- Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy
Cited by in corpus (17)
- Computational advantage of quantum random sampling
- Theory of quantum system certification: a tutorial
- Efficient Verification of Pure Quantum States in the Adversarial Scenario
- On the Quantum versus Classical Learnability of Discrete Distributions
- General framework for verifying pure quantum states in the adversarial scenario
- Verification of phased Dicke states
- Robust and efficient verification of graph states in blind measurement-based quantum computation
- Efficient verification of Affleck-Kennedy-Lieb-Tasaki states
- Dense Coding with Locality Restriction for Decoder: Quantum Encoders vs. Super-Quantum Encoders
- Extracting perfect GHZ states from imperfect weighted graph states via entanglement concentration
- Efficient Verification of Ground States of Frustration-Free Hamiltonians
- Divide-and-conquer verification method for noisy intermediate-scale quantum computation
- Fault-tolerant compiling of classically hard IQP circuits on hypercubes
- In situ characterization of linear-optical networks in randomized boson sampling
- Catalytic Transformation from Computationally Universal to Strictly Universal Measurement-Based Quantum Computation
- Quantum advantage in temporally flat measurement-based quantum computation
- Sampling and the complexity of nature