⚛️ quantum physics

Exact Diagonal Completion on Reachable Subspaces: Application to QAOA Placement

This paper proposes an exact diagonal completion method using weighted- $\ell_1$ optimization to reduce quantum circuit depth for QAOA-based placement problems by exploiting unused encoding states, achieving significant CX gate reductions in specific synthesis contexts but failing to demonstrate a definitive end-to-end advantage over classical approaches.

Original authors: Owen Friedewald, Ali Shiri Sichani, Chi-Ren Shyu

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Owen Friedewald, Ali Shiri Sichani, Chi-Ren Shyu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of quantum computing, researchers are constantly trying to solve complex puzzles by arranging tiny particles called qubits. One of the most promising methods for this is a technique known as the Quantum Approximate Optimization Algorithm, or QAOA. Think of this algorithm as a traveler trying to find the shortest path through a vast, foggy landscape. The traveler does not need to see the entire map to find a good route; they only need to explore the specific trails that are actually open to them. However, the mathematical tools used to guide this traveler are often built to work on a map that is much larger than the actual terrain, including many paths that the traveler can never reach. This creates a problem: the computer has to carry around heavy, unnecessary baggage—extra calculations for paths that don't exist—which slows everything down and uses up precious energy.

A team of researchers at the University of Missouri has found a way to lighten this load. They focused on a specific type of puzzle called "placement," which involves arranging electronic components on a chip to minimize the length of the wires connecting them. In their study, they discovered that because the quantum computer can only visit a small fraction of the possible arrangements, the mathematical instructions for the journey could be rewritten. By filling in the blanks of these instructions with values that don't change the final result but make the math simpler, they could strip away unnecessary steps. They tested this idea across 160 different geometric layouts and found that, under specific conditions, this "cleaning up" of the instructions significantly reduced the number of basic operations the computer needed to perform.

The researchers approached this by looking at how the quantum computer stores information about the location of each component. They used a method where the computer holds a list of possible spots, some of which are occupied by real parts and others that are empty. When the computer swaps these parts around to find a better arrangement, it must ensure it never creates an illegal situation, like two parts trying to sit in the same spot. The team realized that the mathematical formula used to calculate the distance between parts had entries for every possible combination of spots, including those that were impossible to reach. They treated these impossible entries as "don't care" values. Instead of leaving them as zeros or guessing, they used a sophisticated optimization process to choose values that would make the final circuit as small as possible.

When they applied this method to their test cases, the results were striking for certain setups. On layouts where the number of available spots was not a perfect power of two, leaving some spots unused, the new method reduced the number of required two-qubit connections by as much as 53.9 percent compared to standard ways of filling in the blanks. This reduction was consistent across 96 different test cases where unused codes were present. However, the researchers were careful to note that this advantage was not universal. When they used a different, more general way of building the circuit, the savings shrank dramatically, dropping to less than one percent in some cases. This showed that the benefit of their new method depended heavily on the specific tools used to translate the math into a working circuit.

Beyond just making the circuit smaller, the team looked at whether this actually helped the computer solve the placement problem better. They ran simulations comparing their new method against older, more established techniques. While their approach did produce better results in some specific scenarios, particularly with smaller setups involving four components, it did not consistently outperform the traditional methods. In many cases, the older methods, which were allowed to use more layers of operations, performed just as well or better. The researchers also tested whether the placements found by their quantum method could be used in a real-world design flow. They successfully integrated 72 different local placements into a standard chip-design software, and all of them passed the necessary checks for routing wires without errors. This proved that the method produced valid, usable results, even if it did not yet prove to be a superior solver compared to classical computers.

The study ultimately highlights a crucial lesson for the field: finding a shortcut in the math does not automatically guarantee a faster or better solution in the real world. The researchers found that while their technique successfully trimmed the fat from the quantum circuit, the overall performance was still limited by other factors, such as the complexity of the mixing operations and the physical connections between the qubits. They concluded that while this "exact diagonal completion" is a powerful tool for simplifying specific parts of a quantum algorithm, it is just one piece of a much larger puzzle. The path to a truly superior quantum solver for chip design will require balancing these circuit savings with the costs of the rest of the system, and for now, classical computers remain the stronger choice for these tasks. The work serves as a clear demonstration that in quantum computing, every optimization must be measured in the context of the entire machine, not just in isolation.

Technical Summary: Exact Diagonal Completion on Reachable Subspaces: Application to QAOA Placement

Problem Statement

Quantum circuits are often synthesized from operators defined on the full Hilbert space, even when the algorithm is restricted to a small reachable subspace. For diagonal cost operators, entries corresponding to unreachable computational-basis states do not affect the ideal algorithm's output. However, the choice of these "unspecified" diagonal entries constitutes a compilation opportunity. Different exact extensions of the same required action can yield different Walsh spectra and, consequently, different circuit costs (gate counts). The paper investigates this "exact diagonal completion" problem specifically for the Quantum Approximate Optimization Algorithm (QAOA) applied to the circuit placement problem, where the goal is to assign circuit cells to physical sites while minimizing interconnection lengths.

Methodology

The authors propose a framework to optimize the unspecified entries of the distance operator (Manhattan distance) before applying circuit synthesis.

Encodings and Reachable Subspaces:
- One-hot Encoding: Uses $nm$ qubits with XY mixers (complete or ring) preserving row excitation.
- Token Permutation Encoding: Uses $n$ real-cell registers and $m-n$ distinguishable "EMPTY" token registers, each of size $k = \lceil \log_2 m \rceil$ . This encoding preserves the permutation of valid site labels via register swaps (Fredkin gates), ensuring all measured placements are legal. The token circuit uses fewer qubits than one-hot only when $mk+1 < nm$; however, increasing the number of vacancies can eliminate or reverse this width benefit (e.g., at four cells and sixteen sites, the token circuit uses 65 qubits versus 64 for one-hot).
Exact Diagonal Completion:
- The distance operator is extended to invalid binary codes (unused labels) to minimize the circuit cost.
- Weighted- $\ell_1$ Completion (L1): The authors formulate a linear program (LP) to find Walsh coefficients $c_j$ that minimize a weighted $\ell_1$ norm (sparsity surrogate) subject to matching the Manhattan distance on all valid site pairs. This is a "weighted basis pursuit" approach.
- Structured Recurrence: For regular coordinate-indexed arrays, a sparse recurrence relation is derived to construct exact distance phases without solving the dense LP, requiring only $O(\sqrt{m})$ terms on balanced rectangles.
Synthesis Strategies:
- The resulting Walsh coefficients are synthesized into circuits using Gray synthesis, which groups terms by their highest-index qubit and traverses control masks in reflected Gray-code order to maximize cancellation of adjacent CNOT (CX) gates.
- Comparisons are made against zero-padding, virtual-coordinate extensions, nearest-code extensions, and mean-fill extensions, as well as against generic diagonal synthesis methods (Qiskit, PyZX).
Experimental Design:
- Cohorts: 160 geometries (100 initial, 60 replication) with 4 cells and varying site counts ( $m=6, 8, 9, 12, 16$ ).
- Metrics: CX gate counts, circuit depth, and placement quality (optimum probability, expected best cost).
- Integration: A separate study integrates selected QAOA placements into the OpenROAD physical design flow to verify legality and downstream feasibility.

Key Contributions

Construction of Exact Manhattan-Distance Phases: The authors construct exact distance phases using a weighted- $\ell_1$ linear program and a sparse coordinate recurrence. They prove that these constructions agree with the required action on all reachable states, regardless of the values assigned to unreachable states.
Synthesis-Dependent Gate Savings: Across 160 geometries, the L1 completion reduces CX counts relative to four alternative extensions in all 96 cases with unused binary codes under Gray synthesis. However, the paper highlights that these gains are highly dependent on the synthesis method; under generic diagonal synthesis, reductions drop significantly (e.g., from 53.9% to 1.3% at 9 sites).
Full-Circuit Resource Analysis: The study evaluates the impact of phase savings on the complete circuit. While L1 completion reduces the phase component's gate count, the overall resource advantage is limited by mixer depth and serialization. Parallel mixing reduces token circuit depth but does not consistently outperform one-hot baselines in total depth or gate count across all hardware topologies.
Placement Quality and Integration: Ideal simulations show baseline-dependent solution quality, with classical search often outperforming QAOA on the tested small instances. However, the paper demonstrates a concrete integration path: 72 QAOA-generated local placements from six RTL designs successfully passed clock-tree synthesis and global routing in OpenROAD with zero overflow.

Results

Gate Reduction: Under Gray synthesis, L1 completion achieves median CX reductions of 28.0%, 53.9%, and 21.6% relative to virtual-coordinate extension for 6, 9, and 12 sites, respectively.
Synthesis Sensitivity: When using generic diagonal synthesis (fixed angles), the advantage of L1 completion diminishes drastically (e.g., 10.9%, 1.3%, 0.7% reductions), demonstrating that the benefit is not compiler-independent.
Resource Trade-offs: Token circuits with L1 completion have fewer data qubits than one-hot only when the number of vacancies is small; as vacancies increase, the width benefit can be lost or reversed (e.g., 65 qubits vs 64 for one-hot at 4 cells/16 sites). Additionally, token circuits often have deeper circuits due to swap networks. Parallelizing swaps reduces depth by ~20-24% but does not establish a universal resource advantage over one-hot encodings.
Solution Quality: At matched circuit costs, token encodings show higher optimum probabilities than one-hot baselines in some 4-cell cases, but this advantage does not hold consistently across larger sizes (5-6 cells) or different training regimes. Classical multi-start greedy search consistently finds better solutions than QAOA on the tested instances.
Downstream Feasibility: All 72 QAOA placements and 216 classical placements in the OpenROAD study completed clock-tree synthesis and global routing with zero overflow, validating the legality of the generated placements for physical design.

Significance and Claims

The paper modestly claims that exact diagonal completion is a viable circuit-design decision that can reduce implementation costs without altering the ideal algorithm's behavior. The authors emphasize that:

Freedom is Real but Contextual: The ability to choose unspecified diagonal entries offers real opportunities for optimization, but the magnitude of the benefit is tightly coupled with the synthesis method and the specific encoding.
No End-to-End Advantage Established: While phase construction is improved, the paper does not establish a quantum advantage for placement. The full-circuit results show that mixer costs, connectivity, and the difficulty of training variational circuits often negate the phase-level savings.
Integration Path: The primary practical contribution is demonstrating that QAOA can generate legal, high-quality local placements that are compatible with standard electronic design automation (EDA) flows, even if the quantum solver does not yet outperform classical heuristics on these specific small-scale instances.

The work serves as a rigorous evaluation of a specific compilation technique (completion) within a constrained quantum application (placement), clarifying the gap between theoretical operator simplification and practical quantum resource reduction.