PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Layout Synthesis for Quantum Computing

Bochen Tan, Jason Cong

arXiv:2007.15671v1cs.ARquant-ph

TL;DR

Quantum layout synthesis must map logical circuits onto error-prone hardware with restricted connectivity while preserving executable ordering. The paper formulates this task as optimization and develops an exact synthesizer, a nearly optimal transition-based variant, and a commutation-aware QAOA variant. Across benchmark programs and architectures, the methods improve efficiency, cost, fidelity, and— for QAOA—depth relative to prior approaches.

  • Problem

    Existing LSQC methods have substantial optimality gaps, while hardware connectivity and execution constraints make reliable layout synthesis necessary.

  • Method

    The paper formulates LSQC as optimization using spacetime-based variables, presenting OLSQ, transition-based TB-OLSQ, and commutation-aware QAOA-OLSQ.

  • Results

    TB-OLSQ is nearly exact, reduces CX cost by 69.2% in geometric mean versus t|ket⟩, and increases fidelity by up to 10.0x versus TriQ on some larger programs.

  • Takeaways & Limitations

    OLSQ provides stronger optimality and improved efficiency, while TB-OLSQ and QAOA-OLSQ deliver scalable performance across general and QAOA workloads.

  • Takeaways & Limitations

    The formulation assumes gate cancellation or optimization has already occurred and requires all input gates to be executed.

Abstract

from arXiv · show

Recent years have witnessed the fast development of quantum computing. Researchers around the world are eager to run larger and larger quantum algorithms that promise speedups impossible to any classical algorithm. However, the available quantum computers are still volatile and error-prone. Thus, layout synthesis, which transforms quantum programs to meet these hardware limitations, is a crucial step in the realization of quantum computing. In this paper, we present two synthesizers, one optimal and one approximate but nearly optimal. Although a few optimal approaches to this problem have been published, our optimal synthesizer explores a larger solution space, thus is optimal in a stronger sense. In addition, it reduces time and space complexity exponentially compared to some leading optimal approaches. The key to this success is a more efficient spacetime-based variable encoding of the layout synthesis problem as a mathematical programming problem. By slightly changing our formulation, we arrive at an approximate synthesizer that is even more efficient and outperforms some leading heuristic approaches, in terms of additional gate cost, by up to 100%, and also fidelity by up to 10x on a comprehensive set of benchmark programs and architectures. For a specific family of quantum programs named QAOA, which is deemed to be a promising application for near-term quantum computers, we further adjust the approximate synthesizer by taking commutation into consideration, achieving up to 75% reduction in depth and up to 65% reduction in additional cost compared to the tool used in a leading QAOA study.

1 Introduction

Layout synthesis maps logical qubits and schedules gates onto hardware with limited connectivity. The paper introduces optimal and approximate synthesizers to address optimality gaps and efficiency limitations in existing approaches.

  • Motivation: Quantum algorithms require logic synthesis and layout synthesis before execution on physical quantum computers.Logic synthesis translates gates into the hardware library; layout synthesis then maps and schedules them.
  • Motivation: Limited physical connectivity makes layout synthesis necessary even when algorithms assume all-to-all logical connectivity.Physical architectures provide coupling graphs that constrain which two-qubit gates can execute directly.
  • Research gap: Existing LSQC tools exhibit large optimality gaps, motivating continued research into exact and heuristic methods.Prior exact approaches restrict coupling graphs or impose unnecessary constraints, while heuristics leave room for improvement.
  • Contributions: The paper presents two layout synthesizers and evaluates them on a comprehensive set of quantum programs and architectures.The optimal synthesizer is OLSQ, while TB-OLSQ is an approximate transition-based variant.
  • Contributions: OLSQ reduces variables exponentially relative to a leading SMT approach and explores a larger solution space through dependency-based placement.Its mapping-variable encoding reduces runtime and memory use compared with Wille et al.’s approach.

2 Background

LSQC takes a quantum circuit and hardware coupling graph as input, then produces gate spacetime coordinates and a final logical-to-physical mapping. Its constraints enforce hardware connectivity, collision avoidance, and dependency preservation while supporting depth, cost, and fidelity objectives.

  • Inputs and outputs: An LSQC input comprises a quantum circuit of single- and two-qubit gates plus a physical coupling graph.The circuit operates on logical qubits, while the graph specifies physical qubits and their connections.
  • Inputs and outputs: The coupling graph contains physical qubits and undirected connections, with optional measurement, single-qubit, and two-qubit fidelity functions.These fidelity functions map physical qubits or edges to values in [0, 1].
  • Inputs and outputs: LSQC outputs spacetime coordinates for original and inserted SWAP gates together with a final logical-to-physical mapping.Gate time coordinates determine execution order, while space coordinates identify physical qubits or coupling-graph edges.
  • Constraints: Two-qubit gates must use valid coupling-graph edges, gates sharing qubits cannot collide, and dependencies must preserve relative order.The default dependency list is derived from gate pairs acting on the same logical qubit.
  • Objectives: LSQC can optimize depth, additional SWAP-gate count, or fidelity.Depth matters because current physical qubits have limited useful lifetimes, while fidelity matters because quantum computers are error-prone.

3 Related Works

Prior LSQC research includes exact, heuristic, fidelity-aware, and benchmark-driven approaches. The paper argues that gate-by-gate or level-by-level arrangements can impose unnecessary dependencies and cause suboptimal results.

  • Exact solutions: Earlier exact methods optimize mappings or gate costs using grid routing, pseudo-Boolean optimization, SMT, or integer linear programming.These approaches differ in their supported coupling graphs and whether they optimize cost or depth.
  • Exact solutions: Gate-by-gate and level-by-level arrangements can impose additional constraints beyond the dependency graph.In the cited example, Wille et al. use two SWAP gates although one suffices because an implicit dependency reverses the optimal ordering.
  • Heuristic solutions: Heuristic approaches use graph cutting, qubit-distance matching, partitioning with A* search, token-swapping extensions, or reliability matrices.Some methods incorporate gate fidelity into initial mapping or SWAP routing.
  • Benchmarks: QUEKO benchmarks expose large optimality gaps in leading industry tools and motivate further LSQC research.The benchmark suite contains circuits with known optimal solutions.

4 Approach

The proposed approach formulates LSQC around dependencies, coupling-graph structure, spacetime variables, and SWAP operations. It then derives transition-based and program-aware variants to improve efficiency and exploit additional structure.

  • Overview: The approach preprocesses dependencies, defines objectives, encodes variables and constraints, and then introduces transition-based and commutation-aware variants.TB-OLSQ changes the notion of time, while QAOA-OLSQ additionally uses commutation.
  • Preprocessing: The default dependency list contains pairs of gates acting on the same logical qubit, and its longest chain supplies a depth lower bound.The collision list and longest dependency chain are computed during preprocessing.
  • Preprocessing: The method extracts overlapping edge pairs and incident-edge sets from the physical coupling graph.These structures support constraints concerning physical connectivity and simultaneous operations.
  • Variable encoding: Mapping variables assign logical qubits to physical qubits at each time, while time and space coordinates locate gates.Single-qubit gates use physical-qubit locations; two-qubit gates use coupling-graph edges.
  • Variable encoding: SWAP variables indicate whether a SWAP occurs on an edge and record its last occupied time slot.The model supports architecture-dependent SWAP duration through parameter S.

4.3 Constraints

The formulation constrains logical-to-physical mappings, gate placement, SWAP duration, and overlap so that mappings and gate coordinates remain physically consistent.

  • Injective Mapping: The model uses an injective mapping so different logical qubits occupy different physical qubits at each time.
  • Consistency between Mapping and Space Coordinates: Gate locations are constrained both by explicit space coordinates and by the logical-qubit mapping at the gate's time.
  • Proper SWAP Insertion: SWAP gates cannot finish before S−1 time slots, cannot overlap on the same or overlapping edges, and cannot conflict with input gates.The formulation separately constrains overlaps with single-qubit gates and with two-qubit gates on the same or overlapping edges.
  • Proper SWAP Insertion: A SWAP on one edge cannot overlap input two-qubit gates on that edge or on spatially overlapping edges.
  • Mapping Transformations by SWAP Gates: If no SWAP finishes, the mapping remains unchanged; if one finishes, the next mapping is transformed by that SWAP.At most one SWAP can finish at a time because overlapping-edge SWAPs are ruled out.

4.4 Objectives

The formulation supports optimizing depth, SWAP cost, and fidelity, with fidelity converted to an additive log objective and SWAP fidelity derived from architecture-specific gate fidelities.

  • Depth: Depth is defined as the maximum time coordinate among the input gates.
  • SWAP cost: SWAP cost is represented as an objective over inserted SWAP gates.
  • Fidelity: Fidelity optimization uses input gate fidelities and architecture-dependent SWAP fidelity, with logarithms converting multiplication into addition.When a SWAP consists of three CX gates, log f_SWAP = 3 log f_2.

4.5 Complexity Analysis

The formulation has O(NT) variables for regular planar coupling graphs, while retaining an exponentially smaller variable representation than leading alternatives.

  • 15?

4.6 Optimality of OLSQ

OLSQ passes variables, an objective, and constraints to Z3, which returns an optimizing model or reports unsatisfiability. The initial time bound may be insufficient for some architectures.

  • Z3 returns variable values optimizing the specified objective or reports “unsatisfiable” after receiving the formulation.The solver receives the variables, one objective, and the constraints.
  • The initial upper bound T is set to the largest dependency-chain length.
  • Some architectures may have no solution under this bound, as illustrated by the quantum-adder LSQC.

4.7 TB-OLSQ: Rethinking Time Coordinates

TB-OLSQ improves OLSQ efficiency by representing time only between mapping transitions. Its formulation separates input gates from SWAP transitions and searches incrementally for an objective-optimizing solution.

  • Motivation: The quantum-adder example has T = 15, but the mapping changes only once, creating redundant π_t^q variables across unchanged intervals.The full search space is exponential in N and T.
  • Transition-based encoding: TB-OLSQ retains time variables only between transitions, where each transition is a set of parallel SWAP gates.Overlapping SWAP edges cannot share a transition, while non-overlapping edges can.
  • Transition-based encoding: The transition-based execution model interleaves input-gate blocks with SWAP transitions and permits dependency-respecting later gates to move earlier.Consecutive transitions may occur without input gates between them.
  • Formulation: TB-OLSQ changes the formulation so dependent input gates may share a coarse-grain time coordinate, while SWAP gates are handled separately.This sets S = 1 and removes constraints for input–SWAP overlap checking.
  • Search procedure: The solver starts with T = 1 and increases it until feasibility and the selected objective are optimized; resulting depth is T −1.For SWAP cost or fidelity objectives, the solution has at most T −1 transitions.

4.8 QAOA-OLSQ: Removing False Dependencies

QAOA-OLSQ exploits commutation among phase-separation ZZ gates to remove false dependencies. This enables better phase-separation schedules than OLSQ or TB-OLSQ under default dependency assumptions.

  • Commutation-aware synthesis: QAOA-OLSQ derives spacetime coordinates for ZZ and inserted SWAP gates, with depth optimized through TB-OLSQ and OLSQ passes.The method uses commutation to reduce variables and then applies the synthesizers’ optimization stages.
  • QAOA structure: QAOA alternates phase separation using ZZ gates with mixing using Rx gates, while initial Hadamard gates prepare equal superposition.For layout synthesis, the relevant property is which qubits each gate acts on.
  • False dependencies: The original QAOA layout imposes dependencies among all four ZZ gates, preventing OLSQ and TB-OLSQ from reducing depth on IBM QX2.Because the ZZ gates commute, a better phase-separation arrangement can reorder them even when they share qubits.
  • Commutation-aware synthesis: QAOA-OLSQ removes collision constraints during phase separation because all ZZ gates in that stage commute.The resulting blocks use the fewest transitions needed to make required qubit pairs adjacent.
  • Runtime context: Figure 7 compares runtime scaling for Wille et al. and OLSQ-SWAP across architectures ranging from 5 to 16 qubits.The dashed curve is an exponential fit of Wille et al.’s results.

5 Evaluation

The evaluation uses comprehensive benchmarks and compares exact and transition-based synthesizers with leading exact, industry, and academic approaches. OLSQ remains competitive with prior exact methods, while TB-OLSQ achieves near-exact quality with much lower runtime and strong cost and fidelity results.

  • Experimental setup: The evaluation uses comprehensive benchmarks, IBM QX2 and IBM Melbourne fidelity profiles, and Qiskit-based products of gate fidelities.The authors also release the benchmarks and detailed results open-source.
  • OLSQ versus previous optimal approaches: OLSQ-SWAP matches or sometimes exceeds Wille et al. on every benchmark instance under the comparable SWAP-cost objective.The comparison uses bidirectional coupling graphs converted into two directed edges for Wille et al.’s software.
  • OLSQ versus previous optimal approaches: Wille et al.’s runtime is nearly exponential, whereas OLSQ-SWAP shows no exponential runtime growth in the evaluated examples.Wille et al.’s permutation-based preprocessing can require 2TB for N = 12, and several 16-qubit evaluations exceed the 32GB memory limit.
  • OLSQ versus previous optimal approaches: OLSQ-SWAP reaches optimal SWAP cost (0) within a relatively short period on the evaluated Aspen-4 and QUEKO instances.The corresponding Wille et al. evaluations were aborted after exceeding the configured memory limit.
  • TB-OLSQ versus heuristic approaches: TB-OLSQ shows no observable CX-cost degradation versus OLSQ-SWAP and solves queko_15_1 in 30 seconds instead of 9E4 seconds.TB-OLSQ-SWAP reduces CX cost versus t|ket⟩ by 69.2% in geometric mean, while TB-OLSQ-Fidelity reaches up to 10.0x fidelity versus TriQ.

6 Conclusion and Future Work

The paper formulates layout synthesis as optimization and presents exact, transition-based, and commutation-aware synthesizers. The reported results show strong performance across objectives, while the formulation is positioned for broader objectives and program or architecture knowledge.

  • Conclusion: OLSQ is an exact synthesizer, TB-OLSQ is an approximate transition-based synthesizer, and QAOA-OLSQ adds commutation awareness for QAOA programs.The paper reports guaranteed optimality and time- and space-efficiency for OLSQ on general quantum processors.
  • Conclusion: TB-OLSQ shows no visible degradation from OLSQ and outperforms leading academic and industry works on multiple metrics.QAOA-OLSQ reduces both cost and depth in a real QAOA experiment setting.
  • Future work: The formulation supports different objectives and may be extended to objectives involving correlated errors.The authors also identify prior knowledge of program commutation relations and coupling-graph structure as improvement opportunities.
  • Significance: Layout synthesizers target lower depth and cost and higher fidelity for volatile and error-prone quantum computers.The paper links reduced depth with coherence-time improvement.
Loading 2007.15671v1…