Measurement-based classical computation

Abstract

Measurement-based quantum computation (MBQC) is a model of quantum computation, in which computation proceeds via adaptive single qubit measurements on a multi-qubit quantum state. It is computationally equivalent to the circuit model. Unlike the circuit model, however, its classical analog is little studied. Here we present a classical analog of MBQC whose computational complexity presents a rich structure. To do so, we identify uniform families of quantum computations (refining the circuits introduced by Bremner, Jozsa and Shepherd in Proc. R. Soc. A 467, 459 (2011)) whose output is likely hard to exactly simulate (sample) classically. We demonstrate that these circuit families can be efficiently implemented in the MBQC model without adaptive measurement, and thus can be achieved in a classical analog of MBQC whose resource state is a probability distribution which has been created quantum mechanically. Such states (by definition) violate no Bell inequality, but nevertheless exhibit non-classicality when used as a computational resource - an imprint of their quantum origin.

5+3 pages, 2 figures. Latest version has a new title and has been rewritten to talk about other possible resource states. Accepted for publication in Physical Review Letters

References in corpus (4)

• The classical-quantum boundary for correlations: discord and related measures
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Universal resources for measurement-based quantum computation
• Computational power of correlations

Cited by in corpus (26)

• Average-case complexity versus approximate simulation of commuting quantum computations
• Contextuality and Wigner function negativity in qubit quantum computation
• Architectures for quantum simulation showing a quantum speedup
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Boson-Sampling in the light of sample complexity
• Diagonal unitary entangling gates and contradiagonal quantum states
• Quantum Correlations in Nonlocal BosonSampling
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• The complexity of simulating constant-depth BosonSampling
• Noncontextuality Inequalities from Antidistinguishability
• Non-Unitary Quantum Computation in the Ground Space of Local Hamiltonians
• Derandomizing quantum circuits with measurement based unitary designs
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
• Exact and Efficient Simulation of Concordant Computation
• Universal resources for quantum computing
• Coherent-cluster-state generation in networks of degenerate optical parametric oscillators
• Quantum tomography with random diagonal unitary maps and statistical bounds on information generation using random matrix theory
• Unitary $t$-designs from $relaxed$ seeds
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Quantum advantage in temporally flat measurement-based quantum computation
• Quantum formalism on the plane: POVM-Toeplitz quantization, Naimark theorem and linear polarisation of the light
• Discord in relation to resource states for measurement-based quantum computation
• Contextuality, superlocality and nonclassicality of supernoncontextuality
• Reducing depth and measurement weights in Pauli-based computation
• The Computational Power of Non-interacting Particles