Generalized swap networks for near-term quantum computing

Abstract

The practical use of many types of near-term quantum computers requires accounting for their limited connectivity. One way of overcoming limited connectivity is to insert swaps in the circuit so that logical operations can be performed on physically adjacent qubits, which we refer to as solving the `routing via matchings' problem. We address the routing problem for families of quantum circuits defined by a hypergraph wherein each hyperedge corresponds to a potential gate. Our main result is that any unordered set of $k$-qubit gates on distinct $k$-qubit subsets of $n$ logical qubits can be ordered and parallelized in $O(n^{k-1})$ depth using a linear arrangement of $n$ physical qubits; the construction is completely general and achieves optimal scaling in the case where gates acting on all $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ sets of $k$ qubits are desired. We highlight two classes of problems for which our method is particularly useful. First, it applies to sets of mutually commuting gates, as in the (diagonal) phase separators of Quantum Alternating Operator Ansatz (Quantum Approximate Optimization Algorithm) circuits. For example, a single level of a QAOA circuit for Maximum Cut can be implemented in linear depth, and a single level for $3$-SAT in quadratic depth. Second, it applies to sets of gates that do not commute but for which compilation efficiency is the dominant criterion in their ordering. In particular, it can be adapted to Trotterized time-evolution of fermionic Hamiltonians under the Jordan-Wigner transformation, and also to non-standard mixers in QAOA. Using our method, a single Trotter step of the electronic structure Hamiltonian in an arbitrary basis of $n$ orbitals can be done in $O(n^3)$ depth while a Trotter step of the unitary coupled cluster singles and doubles method can be implemented in $O(n^2\eta )$ depth, where $\eta$ is the number of electrons.

Cited by in corpus (33)

• Quantum computational chemistry
• The Variational Quantum Eigensolver: a review of methods and best practices
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers
• Virtual Distillation for Quantum Error Mitigation
• Emerging quantum computing algorithms for quantum chemistry
• Parametric-resonance entangling gates with a tunable coupler
• Variational approaches to constructing the many-body nuclear ground state for quantum computing
• Majorana loop stabilizer codes for error correction of fermionic quantum simulations
• Overlapped grouping measurement: A unified framework for measuring quantum states
• Optimal Qubit Mapping with Simultaneous Gate Absorption
• Hybrid quantum-classical algorithm for computing imaginary-time correlation functions
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• Approximating the quantum approximate optimization algorithm with digital-analog interactions
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• AGP-based unitary coupled cluster theory for quantum computers
• Topological-Graph Dependencies and Scaling Properties of a Heuristic Qubit-Assignment Algorithm
• Low-depth simulations of fermionic systems on square-grid quantum hardware
• Tailored and Externally Corrected Coupled Cluster with Quantum Inputs
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
• Accelerating Quantum Algorithms with Precomputation
• Planning for Compilation of a Quantum Algorithm for Graph Coloring
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Local, Expressive, Quantum-Number-Preserving VQE Ansatze for Fermionic Systems
• Analytical Ground- and Excited-State Gradients for Molecular Electronic Structure Theory from Hybrid Quantum/Classical Methods
• ChemiQ: A Chemistry Simulator for Quantum Computer
• Noise reduction using past causal cones in variational quantum algorithms
• Discontinuous Galerkin discretization for quantum simulation of chemistry
• Classically-Boosted Variational Quantum Eigensolver
• Qubit coupled cluster singles and doubles variational quantum eigensolver ansatz for electronic structure calculations
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models
• Optimized fermionic SWAP networks with equivalent circuit averaging for QAOA
• State-dependent Routing Dynamics in Noisy Quantum Computing Devices