Quantum advantage in temporally flat measurement-based quantum computation

Abstract

Several classes of quantum circuits have been shown to provide a quantum computational advantage under certain assumptions. The study of ever more restricted classes of quantum circuits capable of quantum advantage is motivated by possible simplifications in experimental demonstrations. In this paper we study the efficiency of measurement-based quantum computation with a completely flat temporal ordering of measurements. We propose new constructions for the deterministic computation of arbitrary Boolean functions, drawing on correlations present in multi-qubit Greenberger, Horne, and Zeilinger (GHZ) states. We characterize the necessary measurement complexity using the Clifford hierarchy, and also generally decrease the number of qubits needed with respect to previous constructions. In particular, we identify a family of Boolean functions for which deterministic evaluation using non-adaptive MBQC is possible, featuring quantum advantage in width and number of gates with respect to classical circuits.

References in corpus (66)

• Quantum Computing in the NISQ era and beyond
• Bell nonlocality
• Quantum Teleportation is a Universal Computational Primitive
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Information Causality as a Physical Principle
• Synthesis of Quantum Logic Circuits
• On the role of entanglement in quantum computational speed-up
• Contextuality supplies the magic for quantum computation
• Non-local correlations as an information theoretic resource
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• All multipartite Bell correlation inequalities for two dichotomic observables per site
• Positive Wigner functions render classical simulation of quantum computation efficient
• Quantum advantage with shallow circuits
• A limit on nonlocality in any world in which communication complexity is not trivial
• Average-case complexity versus approximate simulation of commuting quantum computations
• Bell-type inequalities to detect true n-body non-separability
• Efficient decomposition of quantum gates
• Universal resources for measurement-based quantum computation
• Quantum communication complexity of symmetric predicates
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Computational power of correlations
• Instantaneous Quantum Computation
• Contextuality as a resource for models of quantum computation on qubits
• Quantum advantage with noisy shallow circuits in 3D
• Verifying Multipartite Entangled GHZ States via Multiple Quantum Coherences
• Efficient synthesis of universal Repeat-Until-Success circuits
• Determinism in the one-way model
• Generalized Flow and Determinism in Measurement-based Quantum Computation
• Discrete Wigner functions and quantum computational speedup
• Efficient quantum algorithms for $GHZ$ and $W$ states, and implementation on the IBM quantum computer
• Architectures for quantum simulation showing a quantum speedup
• Testing the Structure of Multipartite Entanglement with Bell Inequalities
• Scalable Bell inequalities for qubit graph states and robust self-testing
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits
• Efficient synthesis of probabilistic quantum circuits with fallback
• Non-adaptive Measurement-based Quantum Computation and Multi-party Bell Inequalities
• T-count optimization and Reed-Muller codes
• Semi-Clifford operations, structure of ${\mathcal{C}}_k$ hierarchy, and gate complexity for fault-tolerant quantum computation
• Contextuality as a resource for measurement-based quantum computation beyond qubits
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Measurement-based classical computation
• Quantum interference enables constant-time quantum information processing
• Lower bounds on the entanglement needed to play XOR non-local games
• Multivariate trace estimation in constant quantum depth
• Quantum advantage for computations with limited space
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Mermin's Inequalities of Multiple qubits with Orthogonal Measurements on IBM Q 53-qubit system
• Experimental demonstration of the violations of Mermin's and Svetlichny's inequalities for W- and GHZ-class of states
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Classical multiparty computation using quantum resources
• Average-Case Quantum Advantage with Shallow Circuits
• Efficient quantum gate teleportation in higher dimensions
• Correlations for computation and computation for correlations
• Testing Scalable Bell Inequalities for Quantum Graph States on IBM Quantum Devices
• Playing quantum nonlocal games with six noisy qubits on the cloud
• Quantum computational advantage attested by nonlocal games with the cyclic cluster state
• Enhanced delegated computing using coherence
• Measurable criteria of generalized non-locality under the correlation symmetry
• Hierarchies of resources for measurement-based quantum computation
• The power of qutrits for non-adaptive measurement-based quantum computing
• Is Communication Complexity Physical?
• Quantum advantage from energy measurements of many-body quantum systems
• Cost-optimal single-qubit gate synthesis in the Clifford hierarchy
• Classification of measurement-based quantum wire in stabilizer PEPS
• Quantum Advantage with Shallow Circuits Under Arbitrary Corruption