The Hadamard gate cannot be replaced by a resource state in universal quantum computation
arXiv:2312.03515 · doi:10.22331/q-2024-09-11-1470
Abstract
We consider models of quantum computation that involve operations performed on some fixed resourceful quantum state. Examples that fit this paradigm include magic state injection and measurement-based approaches. We introduce a framework that incorporates both of these cases and focus on the role of coherence (or superposition) in this context, as exemplified through the Hadamard gate. We prove that given access to incoherent unitaries (those that are unable to generate superposition from computational basis states, e.g. CNOT, diagonal gates), classical control, computational basis measurements, and any resourceful ancillary state (of arbitrary dimension), it is not possible to implement any coherent unitary (e.g. Hadamard) exactly with non-zero probability. We also consider the approximate case by providing lower bounds for the induced trace distance between the above operations and Hadamard gates. To demonstrate the stability of this result, this is then extended to a similar no-go result for the case of using Hadamard gates to exactly implement Hadamard gates.
31 pages, 3 figures. Latest version includes an improved bound for Lemma 19, added references, data access statement, and amended grant code. Accepted in Quantum
References in corpus (37)
- Quantum entanglement
- Quantum information with continuous variables
- Quantum Coherence as a Resource
- Adiabatic Quantum Computing
- Improved Simulation of Stabilizer Circuits
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Quantum Resource Theories
- Measurement-based quantum computation
- Quantum Computational Supremacy
- Roads towards fault-tolerant universal quantum computation
- From Classical to Quantum Shannon Theory
- Application of a resource theory for magic states to fault-tolerant quantum computing
- Cluster-state quantum computation
- Randomizing quantum states: Constructions and applications
- Classical simulation of noninteracting-fermion quantum circuits
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Trading classical and quantum computational resources
- An Invitation to Quantum Incompatibility
- Matchgates and classical simulation of quantum circuits
- Converting Nonclassicality into Entanglement
- Quantum Hypergraph States
- A Simple Proof that Toffoli and Hadamard are Quantum Universal
- An introduction to measurement based quantum computation
- Quantifying magic for multi-qubit operations
- Incompatible measurements in quantum information science
- Classical simulation versus universality in measurement based quantum computation
- Resource Theory of Coherence - Beyond States
- Using and reusing coherence to realize quantum processes
- Fundamentals of universality in one-way quantum computation
- Generic bound coherence under strictly incoherent operations
- All pure fermionic non-Gaussian states are magic states for matchgate computations
- Fundamental energy requirement of reversible quantum operations
- Universal resources for approximate and stochastic measurement-based quantum computation
- Universal limitations on implementing resourceful unitary evolutions
- Computational power of matchgates with supplementary resources
- A Herculean task: Classical simulation of quantum computers
- Quantum states cannot be transmitted efficiently classically