On the Distortion of Partitioning Performance by Random Quantum Circuits

arXiv:2605.01974 · quant-ph, cs.DC, cs.ET · Submitted 2026-05-03 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "On the Distortion of Partitioning Performance by Random Quantum Circuits".

Mira: The gist The results show that random circuits significantly distort partitioning evaluation, inflating cut costs, altering scaling trends, and changing strategy rankings compared to real or structured generated circuits.

Kai: First, who's behind it and why it matters.

Paper summary: Kai: So, to get into this paper, "On the Distortion of Partitioning Performance by Random Quantum Circuits," they focus on that common practice where people use random quantum circuits as evaluation workloads because real benchmarks are hard to find. The authors ask directly: is using these random circuits a faithful way to assess how good a hypergraph partitioning strategy really is?

Mira: They set up an experiment testing different partitioning strategies across three circuit origins: real algorithmic circuits, structured generated circuits, and fully random circuits >

Kai: Their main finding is that the results from random circuits are significantly distorted. They inflate the cut costs—which is basically how much communication you need—and they alter the scaling trends when you change the number of QPUs or the size of the circuit >

Mira: Plus, they found that these random circuits change which partitioning strategies rank as better performers, which is a big deal for anyone trying to pick an algorithm >

Lev: If you're thinking about running this on actual quantum hardware, having your performance metrics skewed by random noise in the benchmark setup means you might make wrong assumptions about how efficient your distributed system will actually be >

Kai: The paper contrasts this distortion with structured generated circuits, which they say show substantially lower distortion and track real workload behavior more closely across cost, scaling, and strategy rankings >

Mira: Essentially, they claim that structured generated circuits provide a better bridge between fixed real workloads and structureless random ensembles for testing partitioner training >

Lev: It sounds like the authors are saying that using structured circuits is a more reliable stress test for partitioning heuristics than just throwing random ones at them >

Conclusion: Kai: So, thinking about this whole paper, "On the Distortion of Partitioning Performance by Random Quantum Circuits," it’s really about how our testing methods can be misleading if we rely too heavily on random inputs for benchmarking >

Mira: The authors show that random circuits don't just make the test harder; they change the fundamental way you evaluate performance, inflating costs and messing up strategy comparisons >

Kai: They conclude that structured generated circuits are much more useful because they give you a controllable middle ground between testing with real algorithms and using pure randomness >

Mira: The implication is that if you're designing a compiler for distributed quantum computing, your benchmark choice matters directly in what conclusions you draw about the partitioning algorithm’s merit >

Lev: It’s a warning to the community that random circuits might just provide poor guidance for real compiler design because they don't reflect how structured problems behave >

Kai: So, the takeaway is that we need to move away from using purely random circuits as a primary stress test and instead favor structured generated circuits when you want to see what a partitioning strategy will actually do in practice >

Maria Gragera Garces

Quantum Software Lab, University of Edinburgh

quant-ph, cs.DC, cs.ET

Submitted: 2026-05-03

Updated: 2026-05-11

Code: https://github.com/grageragarces/Random-circuits-for-DQC

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 67/100

The gist: The gist The results show that random circuits significantly distort partitioning evaluation, inflating cut costs, altering scaling trends, and changing strategy rankings compared to real or

Key concepts

Hypergraph Partitioning
This is the core technique used to divide a quantum circuit into smaller pieces for different quantum processors (QPUs). Qubits become vertices, and multi-qubit gates create hyperedges. The goal is to minimize the connections (cut hyperedges) between these partitions, which represents necessary communication overhead.
Circuit Origins
The paper compares three ways quantum circuits are created: real algorithmic circuits (like established algorithms), fully random circuits, and structured generated circuits. These origins determine the underlying entanglement patterns and gate structures, which significantly affect how well a partitioning algorithm performs.
Distortion Metrics
The researchers measured performance distortion across four key areas: cut cost (communication overhead), scaling behavior with more QPUs or circuit size, the relative ranking of different partitioning strategies, and the variability of results. These metrics reveal whether a benchmark accurately reflects how a partitioner will behave in a real distributed quantum computing scenario.

Terminology

Summary

The gist The results show that random circuits significantly distort partitioning evaluation, inflating cut costs, altering scaling trends, and changing strategy rankings compared to real or structured generated circuits.

How it works

Hypergraph partitioning is central to distributed quantum computing (DQC) compilers, where it divides a quantum computation into sub-computations executed across multiple QPUs while minimizing communication overhead The standard abstraction for this problem is the hypergraph representation of a quantum circuit where qubits correspond to vertices and multi-qubit gates induce hyperedges Partitioning this hypergraph yields subcircuits mapped to different devices, while cut hyperedges correspond to required quantum communication primitives such as teleportation or entanglement distribution.

The study investigates whether benchmarking practices using random quantum circuits provide a faithful assessment of partitioner performance The researchers evaluate diverse partitioning strategies across three circuit origins: real algorithmic circuits, structured generated circuits, and fully random circuits.

Partitioning Strategies Evaluated

The methodology evaluates seven distinct hypergraph partitioning strategies to compare their performance These include:

  1. Random partitioner: This assigns each vertex independently and uniformly to one of the k blocks, serving as a baseline.

  2. Greedy partitioner: This deterministic, single-pass method processes hyperedges sequentially by placing unassigned vertices in the block with the majority of that hyperedge’s vertices.

  3. Stochastic Greedy partitioner (StochG): This extends the greedy approach with randomized restarts and local improvement to explore multiple local minima.

  4. Fiduccia-Mattheyses (FM): This implements a k-way extension of the original hypergraph partitioner, utilizing gain calculations for legal moves.

  5. KaHyPar: This is a state-of-the-art multilevel hypergraph partitioner that applies hypergraph coarsening, initial partitioning, and uncoarsening with refinement

Circuit Origins and Distortion Metrics

The evaluation compares partitioners across three circuit origins:

  1. Real circuits: Derived from well-known quantum algorithms like the MQT Benchmark suite or Quipper implementations, exhibiting real structured entanglement patterns.

  2. Random circuits: Generated using Qiskit’s random circuit function generator or graph-based generators implemented on randomly sampled interaction graphs.

  3. Generated circuits: Produced by QGen, which programmatically instantiates well-known algorithms with algorithm-specific generation parameters to control oracle structure and entanglement topology.

Distortion is operationalized along four axes:

** Cut cost (equivalently, Communication cost): the number of cut hyperedges (those whose vertices span more than one partition), each of which requires consuming a nonlocal EPR pair in the distributed setting **

** Scaling behaviour across QPU counts and circuit widths. **

** Relative ranking of partitioning strategies. **

** Variability of results across instances. **

Key Findings on Distortion

The primary observation is that the origin of a circuit significantly affects partitioner performance, with random circuits producing substantially larger total accumulated cut cost than real circuits, which in turn are larger than generated circuits.

Furthermore, variance across partitioning strategies and QPU sizes is considerably higher for random circuits compared to real and generated circuits.

Distortion in relative ranking is pronounced; the Spearman rank correlation between strategy rankings and real circuits is only ρ = 0.543 for random circuits.

Conclusion and Implications

Generated circuits closely track the distribution of real circuits, exhibiting substantial overlap in both spread and central tendency. Overall, generated circuits produce substantially lower cut costs than random circuits and exhibit higher rank agreement with real workloads. This suggests that structured, parameterized circuit generators can serve as scalable stress-test workloads for partitioning heuristics.

The paper concludes that random circuits induce distortion across all four identified axes, indicating they are not only a harder more compute consuming benchmark but also induce a different evaluation regime leading to incorrect assumptions about the relative merit of partitioning strategies. Generated circuits offer a scalable intermediate setting between dense random stress tests and scarce large-scale real applications.

The study suggests that qubit interaction topology is the distinguishing structural property rather than multi-qubit gate count. Future evaluation frameworks should account for circuit-specific structural properties and extend beyond the fully-connected network model to incorporate routing costs.

Improvements for AI systems

  1. textbfIncrease Benchmarking Fidelity for Distributed Quantum Compilers (DQC): The improved system can accurately predict partitioning performance on novel quantum workloads by utilizing structured generated circuits instead of random circuits, as structured generated circuits exhibit substantially lower distortion, more closely approximating real workload behaviour in cost, scaling, and strategy rankings.

  2. textbfContext-Aware Partitioning Strategy Selection: The improved AI system can dynamically select the optimal hypergraph partitioning strategy based on the circuit origin (Real vs. Random vs. Generated), as Ranking distortion is quantified via the Spearman rank correlation [20] of strategy rankings relative to real circuits, allowing it to avoid strategies that perform poorly under a specific workload ensemble, such as observing that FM ranks 5th (not last) for random circuits, and Greedy, last for random.

  3. textbfEarly-Stage Prototyping Efficiency: The system can rapidly prototype partitioning heuristics with generated circuits to achieve substantially lower cut costs than random circuits and exhibit higher rank agreement with real workloads, making it a structurally informed but comparatively less demanding regime for testing.

Related papers