arxiv: 2605.01974 · v2 · submitted 2026-05-03 · 🪐 quant-ph · cs.DC

Recognition: 2 theorem links

· Lean Theorem

On the Distortion of Partitioning Performance by Random Quantum Circuits

Maria Gragera Garces

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:33 UTC · model grok-4.3

classification 🪐 quant-ph cs.DC

keywords hypergraph partitioningdistributed quantum computingrandom quantum circuitsbenchmark distortioncut costsscaling trendsstrategy ranking

0 comments

The pith

Random quantum circuits inflate cut costs, alter scaling trends, and shift partitioning strategy rankings in distributed quantum computing benchmarks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tests whether random quantum circuits, commonly used for benchmarking because real examples are scarce, give faithful assessments of hypergraph partitioning strategies for distributed quantum computing compilers. It runs state-of-the-art partitioners on real algorithmic circuits, structured generated circuits, and fully random circuits, then compares the outcomes. Random circuits produce higher cut costs, different performance scaling with QPU count and circuit size, and different rankings among strategies. Structured circuits track real-circuit behavior much more closely in cost, scaling, and rankings. If correct, this means benchmark choice directly shapes what researchers conclude about good compiler methods.

Core claim

Our results show that random circuits significantly distort partitioning evaluation. They inflate cut costs, alter scaling trends across QPU counts and circuit sizes, and change the relative ranking of partitioning strategies. In contrast, structured generated circuits exhibit substantially lower distortion, more closely approximating real workload behaviour in cost, scaling, and strategy rankings. These findings demonstrate that benchmark selection directly influences methodological conclusions in DQC research and that random circuits may provide misleading guidance for compiler design.

What carries the argument

Comparison of hypergraph partitioning performance across real algorithmic circuits, structured generated circuits, and fully random circuits to measure distortion in cost, scaling, and rankings.

If this is right

Partitioning strategies that appear strong on random circuits may rank differently or perform worse on real workloads.
Scaling predictions for systems with varying numbers of QPUs or circuit sizes may be inaccurate when derived from random-circuit tests.
Relative rankings of partitioning methods shift when moving from random to real or structured circuits.
Structured generated circuits can serve as a lower-distortion proxy for real circuits in future partitioning evaluations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Prior DQC partitioning studies that relied on random circuits may require re-testing with real or structured examples to confirm their conclusions.
Compiler designers should prefer structured or real circuits when validating partitioners to ensure results transfer to practice.
Standard benchmark suites for distributed quantum computing would benefit from including circuits with controlled randomness to isolate distortion effects.

Load-bearing premise

The selected real algorithmic circuits and structured generated circuits represent typical workloads, and performance differences arise primarily from the level of randomness rather than other circuit properties.

What would settle it

Apply the same partitioning strategies to a larger set of actual large-scale algorithmic circuits with matching sizes and gate counts, then check whether the inflation of cut costs and changes in scaling and rankings disappear.

Figures

Figures reproduced from arXiv: 2605.01974 by Maria Gragera Garces.

**Figure 1.** Figure 1: Total cut cost produced by each partitioning strategy view at source ↗

**Figure 2.** Figure 2: Heatmap of partitioning performance spread across view at source ↗

**Figure 3.** Figure 3: Normalised cut cost (relative to the random assignment baseline) as a function of the number of QPUs. view at source ↗

**Figure 4.** Figure 4: Normalised cut cost (relative to the random assignment baseline) as a function of circuit size (number of qubits). view at source ↗

**Figure 5.** Figure 5: Violin plots showing the distribution of total cut view at source ↗

read the original abstract

Hypergraph partitioning is a central component of distributed quantum computing (DQC) compilers. However, due to the limited size of available quantum benchmark suites, many partitioning studies rely on random quantum circuits as evaluation workloads. In this work, we investigate whether such benchmarking practices provide a faithful assessment of partitioner performance. We evaluate a diverse set of state-of-the-art hypergraph partitioning strategies across three circuit origins: real algorithmic circuits, structured generated circuits, and fully random circuits. Our results show that random circuits significantly distort partitioning evaluation. They inflate cut costs, alter scaling trends across QPU counts and circuit sizes, and change the relative ranking of partitioning strategies. In contrast, structured generated circuits exhibit substantially lower distortion, more closely approximating real workload behaviour in cost, scaling, and strategy rankings. These findings demonstrate that benchmark selection directly influences methodological conclusions in DQC research and that random circuits may provide misleading guidance for compiler design.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Random circuits do distort DQC partitioning results compared to real ones, but the paper needs clearer isolation of randomness from other circuit traits.

read the letter

The core finding is that fully random quantum circuits inflate cut costs, shift scaling behavior with more QPUs or larger circuits, and reorder which partitioning strategies look best, while structured generated circuits track real algorithmic workloads more closely. This is a useful empirical warning for anyone using benchmarks in distributed quantum computing compilers. The work improves on typical studies by including actual real circuits rather than relying only on synthetic ones, and the side-by-side comparison across the three categories gives concrete numbers on how much the distortion matters for cost, trends, and rankings. That part is worth paying attention to if you run partitioning experiments. The soft spot is the attribution to randomness itself. Real circuits tend to be low-depth and structured by design, while random ones are high-entropy and often deeper or denser; if those other factors were not balanced across the test sets, the observed differences could come from depth or connectivity patterns rather than randomness per se. The abstract does not detail the structured circuit generation procedure or any matching on non-randomness variables, so the isolation is not yet airtight. If the full methods section shows statistical controls or balanced sampling, that concern shrinks; otherwise it stays as a limit on how strongly we can generalize the advice. This paper is aimed at people building or evaluating DQC partitioning tools who care about benchmark fidelity. A reader setting up scaling studies would pick up practical guidance on avoiding misleading rankings. It is coherent on its own terms and engages the literature on partitioning methods, so it deserves a serious referee even if revisions are needed on the controls and error analysis.

Referee Report

3 major / 1 minor

Summary. The paper evaluates hypergraph partitioning strategies for distributed quantum computing across three circuit categories: real algorithmic circuits, structured generated circuits, and fully random circuits. It claims that random circuits distort performance assessment by inflating cut costs, altering scaling behavior with respect to QPU count and circuit size, and shifting the relative rankings of partitioning methods, whereas structured generated circuits exhibit lower distortion and better approximate real workloads.

Significance. If the empirical distinctions hold after controlling for confounders, the result would be significant for DQC compiler research: it would demonstrate that benchmark choice can reverse methodological conclusions and would support preferring structured or real circuits over random ones for faithful evaluation. The direct comparison of three circuit origins is a concrete strength that could guide future benchmark design.

major comments (3)

The central attribution of observed differences in cut cost, scaling, and rankings specifically to 'randomness' (abstract and results) requires isolation from other circuit properties. The manuscript does not report whether the three categories were balanced on qubit count, depth, gate density, or hypergraph connectivity statistics; without such matching or regression controls, the distortion cannot be confidently ascribed to randomness rather than these systematic differences.
No sample sizes, number of circuits per category, or statistical tests are provided for the reported trends in cut costs and strategy rankings (results section). This omission prevents assessment of whether the claimed inflation and ranking changes are statistically reliable or sensitive to particular circuit instances.
The generation procedure for 'structured generated circuits' is not specified (methods). Without details on how motifs, depth distributions, or entanglement patterns are preserved to approximate real algorithmic circuits while differing only in randomness, it is impossible to evaluate whether these circuits successfully isolate the variable of interest.

minor comments (1)

Figure captions and axis labels should explicitly state the number of circuits and any error bars or confidence intervals used for the plotted cut costs and scaling curves.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their constructive comments, which identify key areas for strengthening the manuscript's rigor and reproducibility. We address each major comment below and will incorporate revisions accordingly.

read point-by-point responses

Referee: The central attribution of observed differences in cut cost, scaling, and rankings specifically to 'randomness' (abstract and results) requires isolation from other circuit properties. The manuscript does not report whether the three categories were balanced on qubit count, depth, gate density, or hypergraph connectivity statistics; without such matching or regression controls, the distortion cannot be confidently ascribed to randomness rather than these systematic differences.

Authors: We acknowledge that the manuscript did not explicitly report balancing statistics or apply formal controls for qubit count, depth, gate density, or hypergraph connectivity. This is a valid concern for attributing differences specifically to randomness. In the revised manuscript, we will add a table in the methods or supplementary material reporting the distributions (means, variances, and ranges) of these properties across the three categories. We will also include a regression analysis or matched-subset comparison to isolate the contribution of randomness while controlling for the other factors. revision: yes
Referee: No sample sizes, number of circuits per category, or statistical tests are provided for the reported trends in cut costs and strategy rankings (results section). This omission prevents assessment of whether the claimed inflation and ranking changes are statistically reliable or sensitive to particular circuit instances.

Authors: We agree that the absence of sample sizes and statistical tests limits the ability to evaluate reliability. The original results section presented aggregate trends without these details. In the revision, we will explicitly state the number of circuits per category and add appropriate statistical tests (e.g., t-tests or non-parametric equivalents for cut costs, and rank correlation or permutation tests for strategy ranking shifts) along with sensitivity analysis to individual circuits. revision: yes
Referee: The generation procedure for 'structured generated circuits' is not specified (methods). Without details on how motifs, depth distributions, or entanglement patterns are preserved to approximate real algorithmic circuits while differing only in randomness, it is impossible to evaluate whether these circuits successfully isolate the variable of interest.

Authors: We accept that the generation procedure for structured generated circuits was insufficiently detailed. In the revised methods section, we will provide a complete, reproducible description of the procedure, including the specific circuit motifs, depth and gate density distributions, entanglement pattern controls, and the precise manner in which randomness is introduced while preserving other structural features. revision: yes

Circularity Check

0 steps flagged

No circularity: purely empirical comparison with no derivations or fitted predictions

full rationale

The paper performs an empirical evaluation of hypergraph partitioning strategies on three categories of quantum circuits (real algorithmic, structured generated, and fully random). It reports observed differences in cut costs, scaling, and strategy rankings without any mathematical derivations, first-principles predictions, parameter fitting, or self-referential constructions. No equations are presented that reduce to inputs by construction, and there are no load-bearing self-citations of uniqueness theorems or ansatzes from prior author work. The central observations are direct measurements on chosen workloads; any concerns about confounding variables (e.g., depth or connectivity) fall under validity rather than circularity. The derivation chain is empty by design, making the work self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on domain assumptions about circuit representativeness rather than new free parameters or invented entities; no numerical fitting or new postulated objects are described.

axioms (2)

domain assumption The selected real algorithmic circuits and structured generated circuits are representative of typical DQC workloads.
These serve as the baseline against which random-circuit distortion is measured.
domain assumption The evaluated hypergraph partitioning strategies are state-of-the-art and fairly implemented.
The paper states it evaluates a diverse set of such strategies.

pith-pipeline@v0.9.0 · 5450 in / 1267 out tokens · 44504 ms · 2026-05-12T03:33:11.349353+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our results show that random circuits significantly distort partitioning evaluation. They inflate cut costs, alter scaling trends across QPU counts and circuit sizes, and change the relative ranking of partitioning strategies.
IndisputableMonolith/Cost/FunctionalEquation washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We evaluate a diverse set of state-of-the-art hypergraph partitioning strategies across three circuit origins: real algorithmic circuits, structured generated circuits, and fully random circuits.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Towards a distributed quantum computing ecosystem,

D. Cuomo, M. Caleffi, and A. S. Cacciapuoti, “Towards a distributed quantum computing ecosystem,”IET Quantum Communication, vol. 1, no. 1, pp. 3–8, 2020

work page 2020
[2]

Review of distributed quantum computing: From single qpu to high performance quantum computing,

D. Barralet al., “Review of distributed quantum computing: From single qpu to high performance quantum computing,”Computer Science Review, 2025

work page 2025
[3]

Automated distribution of quantum circuits via hypergraph partitioning,

P. Andres-Martinez and C. Heunen, “Automated distribution of quantum circuits via hypergraph partitioning,”Physical Review A

work page
[4]

High-quality hypergraph partitioning,

S. Schlaget al., “High-quality hypergraph partitioning,”ACM Journal of Experimental Algorithmics, 2023

work page 2023
[5]

Distributing quantum circuits using teleportations,

R. G. Sundaram and H. Gupta, “Distributing quantum circuits using teleportations,” in2023 IEEE International Conference on Quantum Software (QSW). IEEE, 2023, pp. 186–192

work page 2023
[6]

Efficient distribution of quantum circuits,

R. Sundaram, “Efficient distribution of quantum circuits,” 2021

work page 2021
[7]

A multilevel framework for partitioning quantum circuits,

F. Burt, K.-C. Chen, and K. K. Leung, “A multilevel framework for partitioning quantum circuits,”Quantum, vol. 10, p. 1984, 2026

work page 1984
[8]

Hungarian qubit assignment for optimized mapping of quantum cir- cuits on multi-core architectures,

P. Escofet, A. Ovide, C. G. Almudever, E. Alarc ´on, and S. Abadal, “Hungarian qubit assignment for optimized mapping of quantum cir- cuits on multi-core architectures,”IEEE Computer Architecture Letters, vol. 22, no. 2, pp. 161–164, 2023

work page 2023
[9]

Mapping quantum circuits to modular architectures with qubo,

M. Bandic, L. Prielinger, J. N ¨ußlein, A. Ovide, S. Rodrigo, S. Abadal, H. Van Someren, G. Vardoyan, E. Alarcon, C. G. Almudeveret al., “Mapping quantum circuits to modular architectures with qubo,” in2023 IEEE international conference on quantum computing and engineering (QCE), vol. 1. IEEE, 2023, pp. 790–801

work page 2023
[10]

Quantum supremacy using a programmable superconducting processor,

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buellet al., “Quantum supremacy using a programmable superconducting processor,”nature, vol. 574, no. 7779, pp. 505–510, 2019

work page 2019
[11]

Random quantum circuits,

M. P. Fisher, V . Khemani, A. Nahum, and S. Vijay, “Random quantum circuits,”Annual Review of Condensed Matter Physics, vol. 14, no. 1, pp. 335–379, 2023

work page 2023
[12]

More recent advances in (hyper) graph partition- ing,

¨U. C ¸ ataly¨ureket al., “More recent advances in (hyper) graph partition- ing,”ACM Computing Surveys, vol. 55, no. 12, pp. 1–38, 2023

work page 2023
[13]

A linear-time heuristic for im- proving network partitions,

C. M. Fiduccia and R. M. Mattheyses, “A linear-time heuristic for im- proving network partitions,” inPapers on Twenty-five years of electronic design automation, 1988, pp. 241–247

work page 1988
[14]

Parallel hypergraph partitioning for scientific computing,

K. D. Devine, E. G. Boman, R. T. Heaphy, R. H. Bisseling, and U. V . Catalyurek, “Parallel hypergraph partitioning for scientific computing,” inProceedings 20th IEEE International Parallel & Distributed Process- ing Symposium. IEEE, 2006, pp. 10–pp

work page 2006
[15]

Mqt bench: Benchmarking software and design automation tools for quantum computing,

N. Quetschlich, L. Burgholzer, and R. Wille, “Mqt bench: Benchmarking software and design automation tools for quantum computing,”Quan- tum, 2023

work page 2023
[16]

Quipper: a scalable quantum programming language,

A. S. Green, P. L. Lumsdaine, N. J. Ross, P. Selinger, and B. Valiron, “Quipper: a scalable quantum programming language,” inProceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation, 2013, pp. 333–342

work page 2013
[17]

7978538,https://doi.org/10.5281/zenodo.7978538

G. Aleksandrowiczet al., “Qiskit: An open-source quantum computing framework,”URL https://doi. org/10.5281/zenodo, vol. 2562110, 2019

work page doi:10.5281/zenodo 2019
[18]

Q-gen: A parameterized quantum circuit generator,

Y . Mao, S. Shresthamali, and M. Kondo, “Q-gen: A parameterized quantum circuit generator,”TQE, 2025

work page 2025
[19]

On a test of whether one of two random variables is stochastically larger than the other,

H. B. Mann and D. R. Whitney, “On a test of whether one of two random variables is stochastically larger than the other,”The Annals of Mathematical Statistics, vol. 18, no. 1, pp. 50–60, 1947

work page 1947
[20]

The proof and measurement of association between two things

C. Spearman, “The proof and measurement of association between two things.” 1961

work page 1961