PaperlayerView exact revision on arXiv

Source-linked AI summary

Measurement-Efficient Differentiable Quantum Architecture Search for Combinatorial Optimization

Lukas Theißinger, Thore Gerlach, Christian Bauckhage

arXiv:2610.10351v1quant-phcs.LG

TL;DR

DQAS requires repeated quantum measurements to estimate gradients, making hardware execution costly. This paper exploits diagonal or Clifford circuit structure to reduce eligible gradient measurements without changing the objective. On 3-SAT and MaxCut, it cuts requested gradient shots by about 39–41% with negligible classical overhead.

  • Problem

    DQAS requires repeated circuit executions to estimate objectives and gradients, making measurement overhead a practical hardware bottleneck.

    Source: §I · p. 1

  • Method

    ME-DQAS uses commutation certificates and one-shift rules for eligible gradients while keeping the objective, architecture sampling, and outer update rule unchanged.

    Source: §I · p. 1, C. Measurement-Efficient DQAS · p. 4, §VI · p. 6

  • Results

    41.4% fewer requested θ-gradient shots on 3-SAT and 39.4% fewer on MaxCut; under the same global shot budget, ME-DQAS also produced roughly five additional search updates and better final normalized best-so-far loss.

    Source: A. Protocol and Metrics · p. 6, §VI · p. 6

  • Takeaways & Limitations

    The method reduces requested gradient measurements with negligible classical overhead while preserving the DQAS objective and outer update rule.

    Source: §I · p. 2, §VI · p. 6

    The fraction of eligible gradients depends on the Hamiltonian, gate pool, suffix structure, and hardware noise.

    Source: §VI · p. 6

Abstract

from arXiv · show

Differentiable quantum architecture search (DQAS) is a promising framework for the automated design of quantum circuits, particularly for variational quantum optimization algorithms. However, its practical deployment on quantum hardware is limited by the large number of circuit measurements required during optimization, making hardware execution costly. In this work, we show that for a broad class of combinatorial optimization problems and commonly used rotational gate parameterizations, the measurement cost of DQAS can be significantly reduced without changing the optimization objective. We derive the proposed measurement reduction scheme theoretically and validate it experimentally on 3-SAT and MaxCut benchmark problems. Our approach reduces the requested gradient measurement cost by about 39 to 41% while introducing only negligible classical post-processing overhead, lowering the practical cost of executing DQAS on quantum hardware.

I. INTRODUCTION

DQAS jointly searches circuit architecture and gate parameters, addressing the dependence of fixed-architecture variational algorithms on a manually selected ansatz. This work reduces gradient-measurement cost for diagonal combinatorial Hamiltonians by exploiting circuit structure, while preserving the objective.

II. RELATED WORK

  • Variational algorithms use compact Ising or QUBO encodings for combinatorial problems, while gradient-based training and architecture search require repeated circuit measurements.Prior measurement-grouping strategies target Hamiltonians with many noncommuting Pauli terms; the paper addresses a distinct source of overhead for diagonal Hamiltonians.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • DQAS relaxes discrete circuit choices so architecture weights and continuous gate parameters can be optimized together, unlike fixed-architecture variational algorithms.Related adaptive methods such as ADAPT-VQE instead greedily grow the ansatz from an operator pool using gradient information.Source: §I · p. 1
  • On 3-SAT and MaxCut, the estimator reduces requested gradient-measurement cost by approximately 39–41% with negligible classical post-processing overhead.It replaces two-shift gradient estimates with one-shift estimates when the circuit suffix has the required diagonal or Clifford structure.Source: §I · pp. 1–2

II. RELATED WORK

  • For diagonal Ising and QUBO Hamiltonians, the method targets shifted-circuit count rather than objective-measurement bases, which are already jointly measurable in the computational basis.The approach applies to DQAS circuits with parameterized Pauli-string rotations and leaves the optimization objective unchanged.Source: §I · pp. 1–2, §II · p. 2

III. FUNDAMENTALS

The section presents combinatorial objectives as diagonal cost Hamiltonians and illustrates the construction with 3-SAT. Their diagonal structure allows objective estimation from computational-basis samples.

A. Combinatorial Optimization as a Diagonal Hamiltonian

  • A 3-SAT optimization objective counts violated clauses, and a satisfying assignment exists exactly when its minimum cost is zero.The Hamiltonian assigns each computational-basis state the corresponding classical objective value.Source: A. Combinatorial Optimization as a… · p. 2
  • For 3-SAT, the cost Hamiltonian is a sum of clause terms that are products of I and Z operators, so they commute and are simultaneously diagonal in the computational basis.Each clause term contributes one unit of energy exactly when that clause is violated.Source: A. Combinatorial Optimization as a… · p. 2
  • When Hf is diagonal, the circuit objective can be estimated by sampling bit strings from the output distribution and averaging their classical costs.The output state U(θ)|0⟩ induces the distribution used for this estimate.Source: A. Combinatorial Optimization as a… · pp. 2–3

B. Differentiable Quantum Architecture Search (DQAS)

DQAS samples candidate circuit architectures from a parameterized distribution, optimizes the sampled circuits’ gate parameters, and updates that distribution from their objective values. The section identifies repeated quantum measurements for parameter-shift gradients as the dominant cost.

B. Differentiable Quantum Architecture Search (DQAS)

  • DQAS samples architectures from pϕ(a), optimizes each sampled circuit’s parameters, then uses its objective values to update the architecture distribution.The architecture-distribution gradient is estimated with REINFORCE on a classical processor.Source: B. Differentiable Quantum Architecture… · p. 3
  • For each sampled architecture, DQAS optimizes circuit parameters by minimizing the objective using parameter-shift gradients, with two additional expectation-value estimates per gradient evaluation.This repeated measurement cost grows with the number of sampled architectures and circuit parameters.Source: B. Differentiable Quantum Architecture… · p. 3
  • Repeated quantum measurements, rather than classical architecture optimization, dominate DQAS cost and form a practical bottleneck for near-term hardware.The classical architecture update is negligible in comparison to repeated circuit execution.Source: B. Differentiable Quantum Architecture… · p. 3

A. Pauli-string rotation gradients

For a Pauli-string rotation, the gradient depends only on Hamiltonian terms that anticommute with its generator. When the generator commutes with the dressed observable, the gradient is exactly zero; for Z-only Hamiltonians, the relevant commutation checks are classical preprocessing.

A. Pauli-string rotation gradients

  • When the generator commutes with the dressed observable, the gradient is exactly zero and requires no measurement.Two sufficient tests establish this condition using commutation with the original observable and later gates.Source: A. Pauli-string rotation gradients · p. 3
  • For Z-only Hamiltonians, both sufficient commutation tests use the known Pauli decomposition and add negligible classical preprocessing overhead.The tests check generator commutation against the Hamiltonian's existing Pauli terms.Source: A. Pauli-string rotation gradients · p. 3
  • Only Hamiltonian terms that anticommute with the gate generator contribute to the gradient, which can be estimated with a π/2 parameter shift.The circuit suffix dresses the observable used in this local gradient calculation.Source: A. Pauli-string rotation gradients · pp. 3–4

B. Cheaper gradients for Z-only Hamiltonians

Computational-basis-diagonal combinatorial optimization Hamiltonians have a Pauli decomposition specified by the problem instance. This structure supports lower-cost gradient estimation without constructing or measuring a new Hamiltonian decomposition.

B. Cheaper gradients for Z-only Hamiltonians

  • Diagonal Hamiltonians for 3-SAT, MaxCut, QUBO, Ising models, and graph coloring have Pauli decompositions specified by the problem instance.For 3-SAT, the terms are Z-type Pauli strings.Source: B. Cheaper gradients for Z-only… · p. 4

1) Commuting suffix:

When every gate after the differentiated gate commutes with the original Hamiltonian, the dressed Hamiltonian reduces to the original diagonal Hamiltonian. The gradient then uses one shifted circuit and only the Hamiltonian terms that anticommute with the gate generator.

1) Commuting suffix:

  • One shifted circuit evaluation replaces the standard two-shift parameter-shift rule when the suffix commutes with H.Only anticommuting Hamiltonian terms contribute, and they remain measurable in the computational basis.Source: 1) Commuting suffix · p. 4

2) Clifford suffix:

A Clifford suffix can support a one-shift gradient estimate even when it does not commute with the Hamiltonian. ME-DQAS applies structural checks to select zero-measurement, one-shift, or standard two-shift estimates while retaining the DQAS objective and update structure.

2) Clifford suffix:

  • A Clifford suffix can enable a one-shift gradient estimate even when it does not commute with H.The estimate uses a shifted circuit with the suffix; physically applying a shallow suffix may be preferable when classical handling would require extra measurement groups.Source: 2) Clifford suffix · p. 4

C. Measurement-Efficient DQAS

  • ME-DQAS checks each gate for a zero-gradient certificate, then for a one-shift suffix condition, and otherwise uses the standard two-shift rule.The checks are structural and do not change the objective; only θ-gradient estimation differs from ordinary DQAS.Source: C. Measurement-Efficient DQAS · p. 4
  • The probability of using a cheaper branch depends on the problem and architecture: diagonal or sparse Hamiltonians and commuting or Clifford gates favor it, while dense Hamiltonians and non-Clifford mixing gates work against it.Longer suffixes can break the required structure, although searched architectures may also learn suffixes rich in commuting or Clifford gates.Source: C. Measurement-Efficient DQAS · pp. 4–5
  • Fig. 1 compares baseline DQAS and ME-DQAS on matched 3-SAT and MaxCut instances under the same global shot budget, measuring quality, completed updates, and requested θ-gradient shot cost.The caption specifies means with 95% confidence intervals.Source: Figure 1 · p. 5
  • Exact-zero gradient certificates dominate the requested shot-cost reduction, the diagonal one-shift rule contributes next, and the Clifford-suffix branch is negligible for this gate set.Fig. 2 breaks down the sources of the requested full θ-shot reduction.Source: Figure 2 · p. 5

A. Protocol and Metrics

Paired, shot-budgeted simulations compared ME-DQAS with baseline DQAS on 3-SAT and MaxCut. ME-DQAS reduced requested gradient-shot cost, enabled more updates under the shared budget, and used structural certificates to remove or simplify eligible gradient measurements.

A. Protocol and Metrics

  • Paired runs matched the problem instance, initialization, architecture-distribution seed, batch size, learning rates, and global shot budget across algorithms.The benchmarks used random 3-SAT formulas and MaxCut graphs with m = αn and α ∈ {1.5, 2.0}; n = 8, L = 8, and the global budget was B = 750,000.Source: A. Protocol and Metrics · pp. 5–6
  • The reported metrics were final normalized best-so-far loss, completed objective updates, and requested full θ-gradient shot-cost ratio.The 3-SAT loss counts violated clauses, while the MaxCut minimization loss counts uncut edges.Source: A. Protocol and Metrics · pp. 5–6
  • ME-DQAS used 41.4% fewer requested gradient shots on 3-SAT and 39.4% fewer on MaxCut, with roughly five additional updates and lower final normalized loss on both.Requested θ-gradient cost was 0.5857 ± 0.0014 of baseline on 3-SAT and 0.6064 ± 0.0046 on MaxCut; updates were 14.05 ± 0.04 versus 8.99 ± 0.02 and 13.54 ± 0.13 versus 8.56 ± 0.10, respectively.Source: A. Protocol and Metrics · p. 6
  • Most savings came from zero-gradient certificates, while diagonal one-shift rules added savings; the method leaves the objective and outer update rule unchanged.Zero-gradient certificates saved 33.1% of baseline θ-shot cost on 3-SAT and 31.2% on MaxCut; diagonal one-shift rules added 8.3% and 8.1%.Source: A. Protocol and Metrics · p. 6

VI. CONCLUSION

ME-DQAS reduces requested gradient-measurement cost for diagonal combinatorial Hamiltonians while preserving the DQAS objective, architecture sampling, and outer update rule. Paired 3-SAT and MaxCut benchmarks show lower shot cost, more search updates, and better final normalized loss, with savings dependent on problem and circuit structure.

VI. CONCLUSION

  • ME-DQAS uses commutation certificates and one-shift rules to reduce circuit evaluations for eligible θ-gradients while preserving the objective, architecture sampling, and outer update rule.It is presented for diagonal combinatorial Hamiltonians.Source: §VI · p. 6
  • On paired 3-SAT and MaxCut benchmarks, ME-DQAS reduced requested full θ-gradient shot cost to 58.6% and 60.6% of baseline, with roughly five more updates and better final normalized loss.The eligible-gradient fraction depends on the Hamiltonian, gate pool, suffix structure, and hardware noise.Source: §VI · p. 6
  • When the cost Hamiltonian and circuit suffix expose commutation or Clifford structure, eligible DQAS gradients need not use the full two-shift rule.The method's savings vary with the Hamiltonian, gate pool, suffix structure, and hardware noise.Source: §VI · p. 6
Loading 2610.10351v1…