Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation

Abstract

We propose a new composable and information-theoretically secure protocol to verify that a server has the power to sample from a sub-universal quantum machine implementing only commuting gates. By allowing the client to manipulate single qubits, we exploit properties of Measurement based Blind Quantum Computing to prove security against a malicious Server and therefore certify quantum supremacy without the need for a universal quantum computer.

27 pages, 16 figures

References in corpus (5)

• Multi-party entanglement in graph states
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Fault-Tolerant Computing With Biased-Noise Superconducting Qubits
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Completeness of the classical 2D Ising model and universal quantum computation

Cited by in corpus (7)

• Verification of quantum computation: An overview of existing approaches
• Verification of Many-Qubit States
• Sample complexity of device-independently certified "quantum supremacy"
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Efficient verification of Boson Sampling
• Nonadaptive fault-tolerant verification of quantum supremacy with noise
• Methods for Classically Simulating Noisy Networked Quantum Architectures