Verifying commuting quantum computations via fidelity estimation of weighted graph states

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 (10)

• Experimental quantum computing without entanglement
• Quantum Computational Supremacy
• 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
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Experimental Scattershot Boson Sampling
• Robust self testing of the 3-qubit $W$ state
• Sample complexity of device-independently certified "quantum supremacy"
• 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