Reducing depth and measurement weights in Pauli-based computation

Abstract

Pauli-based computation (PBC) is a universal measurement-based quantum computation model steered by an adaptive sequence of independent and compatible Pauli measurements on separable magic-state qubits. Here, we propose several new techniques for reducing the weight of the Pauli measurements and their associated \textsc{cnot} complexity; we also demonstrate how to decrease this model's computational depth. We start by proving new upper bounds on the required weights and computational depth, obtained via a pre-compilation step. We also propose a heuristic algorithm that can contribute reductions of over 30\% to the average weight of Pauli measurements (and associated \textsc{cnot} count) when simulating and compiling Clifford-dominated random quantum circuits with up to 22 $T$ gates and over 20\% for instances with larger $T$ counts. This PBC-compilation scheme, boosted by the heuristic algorithm, outperforms state-of-the-art compilers for the former circuits, reducing the \textsc{cnot} count by 18\% to 96\% compared with the values achieved by other techniques. In contrast, for the latter circuits with larger $T$ counts, it leads to a number of \textsc{cnot}s roughly 30\% larger. Finally, inspired by known state-transfer methods, we introduce incPBC, a universal model for quantum computation requiring a larger number of (now incompatible) Pauli measurements of weight at most 2.

arXiv comment28 pages, 18 figures, includes a link to the GitHub repository where the greedy algorithm can be found

References in corpus (32)

• Elementary gates for quantum computation
• Quantum Teleportation is a Universal Computational Primitive
• Measurement-based quantum computation with cluster states
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Multi-party entanglement in graph states
• Quantum Error Correction and Orthogonal Geometry
• Resource-efficient linear optical quantum computation
• Simulating quantum computation by contracting tensor networks
• Restrictions on Transversal Encoded Quantum Gate Sets
• Trading classical and quantum computational resources
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Quantum Circuit Simplification and Level Compaction
• Universal resources for measurement-based quantum computation
• Universal quantum computation using only projective measurement, quantum memory, and preparation of the 0 state
• Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
• Reducing T-count with the ZX-calculus
• Determinism in the one-way model
• Unified derivations of measurement-based schemes for quantum computation
• Generalized Flow and Determinism in Measurement-based Quantum Computation
• Parallelizing Quantum Circuits
• Hierarchy of universal entanglement in 2D measurement-based quantum computation
• Fundamentals of universality in one-way quantum computation
• Computation by measurements: a unifying picture
• State Transfer instead of Teleportation in Measurement-based Quantum Computation
• T-count optimization and Reed-Muller codes
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Exact and practical pattern matching for quantum circuit optimization
• Measurement-based classical computation
• Reducing 2-QuBit Gate Count for ZX-Calculus based Quantum Circuit Optimization
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Pauli-based model of quantum computation with higher-dimensional systems
• Catalytic Transformation from Computationally Universal to Strictly Universal Measurement-Based Quantum Computation