Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states

Abstract

While the circuit model of quantum computation defines its logical depth or "computational time" in terms of temporal gate sequences, the measurement-based model could allow totally different temporal ordering and parallelization of logical gates. By developing techniques to analyze Pauli measurements on multi-qubit hypergraph states generated by the Controlled-Controlled-Z (CCZ) gates, we introduce a deterministic scheme of universal measurement-based computation. In contrast to the cluster-state scheme, where the Clifford gates are parallelizable, our scheme enjoys massive parallelization of CCZ and SWAP gates, so that the computational depth grows with the number of global applications of Hadamard gates, or, in other words, with the number of changing computational bases. A logarithmic-depth implementation of an N-times Controlled-Z gate illustrates a novel trade-off between space and time complexity.

arXiv comment16 pages, 12 figures,

References in corpus (43)

• Persistent entanglement in arrays of interacting particles
• Quantum Teleportation is a Universal Computational Primitive
• Measurement-based quantum computation with cluster states
• Symmetry protected topological orders and the group cohomology of their symmetry group
• Quantum advantage with shallow circuits
• Implementation of a Toffoli Gate with Superconducting Circuits
• Realization of the quantum Toffoli gate with trapped ions
• Average-case complexity versus approximate simulation of commuting quantum computations
• Entanglement Detection in the Stabilizer Formalism
• Novel schemes for measurement-based quantum computation
• Universal fault-tolerant quantum computation with only transversal gates and error correction
• Complete 3-Qubit Grover Search on a Programmable Quantum Computer
• Universal resources for measurement-based quantum computation
• Measurement-based quantum computation beyond the one-way model
• Quantum circuits of T-depth one
• Nonlocality of cluster states of qubits
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Hypergraph States
• Topological phases with generalized global symmetries
• Unfolding the color code
• Hierarchy of universal entanglement in 2D measurement-based quantum computation
• Verification of Many-Qubit States
• Entanglement and nonclassical properties of hypergraph states
• Encoding Hypergraphs into Quantum States
• Gapped boundaries, group cohomology and fault-tolerant logical gates
• Verified measurement-based quantum computing with hypergraph states
• Efficient Grover search with Rydberg blockade
• Quantum computational webs
• Extreme violation of local realism in quantum hypergraph states
• Latent Computational Complexity of Symmetry-Protected Topological Order with Fractional Symmetry
• Linear and logarithmic time compositions of quantum many-body operators
• Quantum circuits and low-degree polynomials over F_2
• Graph states and local unitary transformations beyond local Clifford operations
• Universal quantum computing using $({\mathbb{Z}}_d{)}^3$ symmetry-protected topologically ordered states
• Universal fault-tolerant quantum computation with Bacon-Shor codes
• Bipartite all-versus-nothing proofs of Bell's theorem with single-qubit measurements
• Quantum and Classical Tradeoffs
• Hypergraph states in Grover's quantum search algorithm
• Graphical description of unitary transformations on hypergraph states
• Local Pauli stabilizers of symmetric hypergraph states
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Quantum Complexity: restrictions on algorithms and architectures

Cited by in corpus (24)

• Many-body quantum magic
• Error protected qubits in a silicon photonic chip
• Subsystem symmetries, quantum cellular automata, and computational phases of quantum matter
• Efficient Verification of Hypergraph States
• General framework for verifying pure quantum states in the adversarial scenario
• Computational universality of symmetry-protected topologically ordered cluster phases on 2D Archimedean lattices
• Universal MBQC with generalised parity-phase interactions and Pauli measurements
• Universal measurement-based quantum computation in a one-dimensional architecture enabled by dual-unitary circuits
• Hypergraph Simplification: Linking the Path-sum Approach to the ZH-calculus
• Symmetric hypergraph states: Entanglement quantification and robust Bell nonlocality
• Universal resources for quantum computing
• Entanglement Purification of Hypergraph States
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Characterization, synthesis, and optimization of quantum circuits over multiple-control $\text{Z}$-rotation gates: A systematic study
• Catalytic Transformation from Computationally Universal to Strictly Universal Measurement-Based Quantum Computation
• Quantum teleportation implies symmetry-protected topological order
• Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements
• Graphical Framework for Non-Gaussian Quantum States
• Finite-Function-Encoding Quantum States
• Randomized hypergraph states and their entanglement properties
• Quantum Theory from Principles, Quantum Software from Diagrams
• Non-symmetric GHZ states: weighted hypergraph and controlled-unitary graph representations
• Dissipative engineering a tripartite Greenberger-Horne-Zeilinger state for neutral atoms
• Efficient classical simulation of cluster state quantum circuits with alternative inputs