Are random pure states useful for quantum computation?

Abstract

We show the following: a randomly chosen pure state as a resource for measurement-based quantum computation, is - with overwhelming probability - of no greater help to a polynomially bounded classical control computer, than a string of random bits. Thus, unlike the familiar "cluster states", the computing power of a classical control device is not increased from P to BQP, but only to BPP. The same holds if the task is to sample from a distribution rather than to perform a bounded-error computation. Furthermore, we show that our results can be extended to states with significantly less entanglement than random states.

No. But we need 5 pages to say why

References in corpus (9)

• Most quantum states are too entangled to be useful as computational resources
• Novel schemes for measurement-based quantum computation
• Universal resources for measurement-based quantum computation
• Measurement-based quantum computation beyond the one-way model
• Computational power of correlations
• Measurement-based quantum computer in the gapped ground state of a two-body Hamiltonian
• Fundamentals of universality in one-way quantum computation
• Quantum computational webs
• Transitions in the computational power of thermal states for measurement-based quantum computation

Cited by in corpus (93)

• Barren plateaus in quantum neural network training landscapes
• Characterizing Quantum Supremacy in Near-Term Devices
• Local random quantum circuits are approximate polynomial-designs
• Most quantum states are too entangled to be useful as computational resources
• Contextuality in Measurement-based Quantum Computation
• Barren Plateaus in Variational Quantum Computing
• Affleck-Kennedy-Lieb-Tasaki State on a Honeycomb Lattice is a Universal Quantum Computational Resource
• Many-body quantum magic
• Variational Quantum Eigensolver with Fewer Qubits
• Entanglement Devised Barren Plateau Mitigation
• The geometric measure of entanglement for symmetric states
• Continuous-variable quantum computing in the quantum optical frequency comb
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Recent advances for quantum classifiers
• Testing the Structure of Multipartite Entanglement with Bell Inequalities
• Ancilla-Driven Universal Blind Quantum Computation
• Phase transitions and localizable entanglement in cluster-state spin chains with Ising couplings and local fields
• The elusive source of quantum effectiveness
• Large Deviation Bounds for k-designs
• Typicality in random matrix product states
• Quantum computation by local measurement
• Symmetry-protected topological phases with uniform computational power in one dimension
• Quantum computational webs
• Extreme violation of local realism in quantum hypergraph states
• Correlations between outcomes of random measurements
• Additivity and non-additivity of multipartite entanglement measures
• Statistical properties of random matrix product states
• Noisy One-Way Quantum Computations: The Role of Correlations
• Classification of Entanglement in Symmetric States
• Concentration of measure for quantum states with a fixed expectation value
• No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems
• Measurement-Based Quantum Computation
• Quantum state reduction for universal measurement based computation
• Experimental measurement-based quantum computing beyond the cluster-state model
• Quantum spin systems for measurement-based quantum computation
• Local convertibility and the quantum simulation of edge states in many-body systems
• Universal measurement-based quantum computation in two-dimensional SPT phases
• Preparing Valence-Bond-Solid states on noisy intermediate-scale quantum computers
• Universal resources for approximate and stochastic measurement-based quantum computation
• Strong entanglement causes low gate fidelity in inaccurate one-way quantum computation
• Quantum computational universality of spin-3/2 Affleck-Kennedy-Lieb-Tasaki states beyond the honeycomb lattice
• Universal quantum computing using $({\mathbb{Z}}_d{)}^3$ symmetry-protected topologically ordered states
• Constructive Feedback of Non-Markovianity on Resources in Random Quantum States
• Operational Metric for Quantum Chaos and the Corresponding Spatiotemporal Entanglement Structure
• Acausal measurement-based quantum computing
• Uniform Decoherence Effect on Localizable Entanglement in Random Multi-qubit Pure States
• Power of one non-clean qubit
• Quantum computation via measurements on the low-temperature state of a many-body system
• Is macroscopic entanglement a typical trait of many-particle quantum states?
• On the negativity of random pure states
• Physical model for the generation of ideal resources in multipartite quantum networking
• Page curves and typical entanglement in linear optics
• Universal structure of measurement-induced information in many-body ground states
• Typical local measurements in generalised probabilistic theories: emergence of quantum bipartite correlations
• Sharp complexity phase transitions generated by entanglement
• Pseudo-randomness and Learning in Quantum Computation
• Generic aspects of the resource theory of quantum coherence
• Are all Gaussian states also cluster states? Essential diagnostic tools for continuous-variable one-way quantum computing
• Symmetric hypergraph states: Entanglement quantification and robust Bell nonlocality
• Universality in Distribution of Monogamy Scores for Random Multiqubit Pure States
• Computational Power and Correlation in Quantum Computational Tensor Network
• Complexity-constrained quantum thermodynamics
• Universal resources for quantum computing
• Entanglement transitions in random definite particle states
• Quantum computational universality of the Cai-Miyake-Dür-Briegel 2D quantum state from Affleck-Kennedy-Lieb-Tasaki quasichains
• Small violations of full correlation Bell inequalities for multipartite pure random states
• Bell's Inequalities: Foundations and Quantum Communication
• Symmetry constraints on temporal order in measurement-based quantum computation
• Computational Notions of Quantum Min-Entropy
• Asymptotic Entanglement Dynamics Phase Diagrams for Two Electromagnetic Field Modes in a Cavity
• Entanglement-fidelity relations for inaccurate ancilla-driven quantum computation
• Mixedness and entanglement for two-mode Gaussian states
• Maximally entangled gapped ground state of lattice fermions
• Quantum teleportation implies symmetry-protected topological order
• Finding resource states of measurement-based quantum computing is harder than quantum computing
• Quantifying entanglement from the geometric perspective
• Twisted graph states for ancilla-driven quantum computation
• Restrictions on shareability of classical correlations for random multipartite quantum states
• Hypercubic cluster states in the phase modulated quantum optical frequency comb
• Strategies for measurement-based quantum computation with cluster states transformed by stochastic local operations and classical communication
• The Quantum Frontier
• Finding maximal quantum resources
• Topos logic in measurement-based quantum computation
• Classical simulation of measurement-based quantum computation on higher-genus surface-code states
• Outcome Independence of Entanglement in One-Way Computation
• Discord in relation to resource states for measurement-based quantum computation
• Average Rényi Entanglement Entropy in Gaussian Boson Sampling
• Phase transitions in (2 + 1)D subsystem-symmetric monitored quantum circuits
• Beyond pure state entanglement for atomic ensembles
• Generation of hypercubic cluster states in 1-4 dimensions in a simple optical system
• Entanglement dynamics and ergodicity breaking in a quantum cellular automaton
• Statistics of Entanglement Transformation with Hierarchies among Catalysts
• Testing equivalence of pure quantum states and graph states under SLOCC