arxiv: 2605.07374 · v1 · submitted 2026-05-08 · 🪐 quant-ph

Recognition: no theorem link

Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators

Sahel Ashhab , Bora Basyildiz

Authors on Pith no claims yet

Pith reviewed 2026-05-11 01:45 UTC · model grok-4.3

classification 🪐 quant-ph

keywords quantum complexityrandom quantum statesunitary operatorsoptimal controlmulti-qudit systemsgate sequencesphysical time

0 comments

The pith

The minimum number of gates needed for random multi-qudit states and unitaries grows exponentially with the number of qudits, while physical control time grows more slowly.

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

The paper compares two measures of difficulty in creating random quantum states and unitary operators on systems of multiple qudits. One measure counts the shortest sequence of elementary one- and two-qudit gates; the other counts the shortest time achievable with optimized physical control fields. Analytic arguments establish that the gate count must grow exponentially with the number of qudits. Numerical optimal-control calculations indicate that the required physical time grows more slowly. The distinction bears on whether truly random quantum operations can be realized in practice and on the gap between random and pseudorandom quantum objects.

Core claim

We show that the computational complexity of random states or unitary operators scales exponentially with the number of qudits. Our numerical results suggest that the physical complexity of preparing random quantum states and unitary operators scales more slowly than the computational complexity.

What carries the argument

The comparison between the shortest universal-gate sequence length and the shortest optimized-control-pulse duration needed to reach a random target in the multi-qudit unitary group.

If this is right

A random multi-qudit state or unitary requires a number of elementary gates that increases exponentially with system size.
The same state or unitary can be reached by physical control pulses whose duration increases more slowly than the gate count.
The separation between the two scalings affects how random operations relate to simpler pseudorandom constructions.
Resource estimates for quantum algorithms that rely on random states must distinguish gate-based and analog-control implementations.

Where Pith is reading between the lines

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

Analog physical control may allow effectively random states to be prepared with resources that do not grow as fast as digital gate sequences.
The result supplies a concrete test for whether random-circuit sampling experiments are limited by gate count or by physical time.
If the slower physical scaling persists at larger sizes, it would change how one designs experiments that aim to sample from the Haar measure.

Load-bearing premise

That the numerical optimal-control calculations locate the true minimum physical time and that the chosen one- and two-qudit gates form a universal set.

What would settle it

A direct calculation or experiment on systems with more qudits that shows the minimal physical time growing exponentially, matching the gate-count scaling.

read the original abstract

We analyze the complexity of synthesizing random states and unitary operators in a multi-qudit system in two paradigms. In one case, we consider the situation in which we manipulate the system by applying a sequence of one- and two-qudit quantum gates that constitute the elementary, and universal, gate set. The minimum number of gates required to perform the desired operation represents the computational complexity. In the other case, we consider the situation in which we manipulate the physical system using physical fields with optimized control pulses. The minimum time required to perform the desired operation represents the physical complexity. In both cases, we use analytical arguments in combination with optimal-control-theory numerical calculations to determine the complexity of random operations. We show that the computational complexity of random states or unitary operators scales exponentially with the number of qudits. Our numerical results suggest that the physical complexity of preparing random quantum states and unitary operators scales more slowly than the computational complexity. We discuss various implications of our results, especially concerning the relationship between random and pseudorandom states and unitary operators.

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

The analytical exponential scaling for gate complexity holds up, but the claim of slower physical scaling rests on OCT numerics that are only upper bounds and may not capture true minima for larger systems.

read the letter

The paper's core distinction is between computational complexity, which they show scales exponentially with qudit number via a dimension-counting argument, and physical complexity, where their optimal-control numerics suggest slower growth. The analytical part is straightforward and solid: the Hilbert space dimension is d^N, so covering random targets requires exponentially many gates from a universal set. That part does not depend on numerics and aligns with known results on gate complexity for generic operations. The numerics extend this by running OCT on small systems to estimate minimal control times for random states and unitaries, then looking at scaling trends. This is a reasonable way to probe the physical side, and the discussion of implications for random versus pseudorandom operations is useful context. The main limitation is that standard OCT methods, including the gradient-based approaches they likely employ, converge to local optima. The reported times are therefore upper bounds on the true minimal time. For random targets the control landscape is high-dimensional, and nothing guarantees that the sub-optimality gap stays constant or shrinks as the number of qudits increases. If the gap grows, the apparent slower scaling could be an artifact. They do not appear to have run extensive multi-start checks or global optimization to bound this effect. The paper is aimed at people working on quantum control limits and the gap between discrete gates and continuous driving. It gives a clear analytical result worth citing and a numerical suggestion that could be sharpened. I would send it to peer review because the analytical claim is clean and the numerics raise a concrete question that referees can evaluate with the full data.

Referee Report

1 major / 2 minor

Summary. The paper analyzes the complexity of synthesizing random multi-qudit quantum states and unitary operators. It proves analytically that the minimum number of one- and two-qudit gates from a universal set (computational complexity) scales exponentially with the number of qudits via dimension-counting arguments. It then uses optimal-control-theory (OCT) numerics to estimate the minimum physical control time (physical complexity) and reports that this scales more slowly than the gate count.

Significance. If the central claims hold, the work usefully separates discrete gate-count complexity from continuous-time physical complexity in quantum synthesis. The analytical exponential scaling result is robust and parameter-free. The numerical suggestion of slower physical scaling, if strengthened, would bear on the practical advantage of direct optimal control over gate decomposition for preparing random states and unitaries, with implications for pseudorandomness and quantum resource preparation.

major comments (1)

[§4] §4 (Numerical results and OCT calculations): the reported minimal times are obtained via gradient-ascent / GRAPE-style OCT. These methods return upper bounds on the true minimal control time; the manuscript provides no convergence diagnostics, multiple random initializations, or landscape analysis showing that the reported times are globally optimal or that any sub-optimality gap remains bounded as the number of qudits grows. Because the headline claim is that physical complexity scales more slowly than the proven exponential computational complexity, this gap is load-bearing.

minor comments (2)

[§3] The abstract and §3 state that the gate set is universal, but the precise definition of the elementary gate set (e.g., whether it includes all single-qudit rotations or only a finite generating set) should be stated explicitly before the counting argument.
[Figures 3-5] Figure captions for the OCT scaling plots should include the number of random targets sampled, the optimization tolerances, and error bars or variance across instances.

Simulated Author's Rebuttal

1 responses · 1 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address the single major comment regarding the numerical optimal-control results in §4 below. The analytical exponential scaling of computational complexity remains unchanged and robust.

read point-by-point responses

Referee: [§4] §4 (Numerical results and OCT calculations): the reported minimal times are obtained via gradient-ascent / GRAPE-style OCT. These methods return upper bounds on the true minimal control time; the manuscript provides no convergence diagnostics, multiple random initializations, or landscape analysis showing that the reported times are globally optimal or that any sub-optimality gap remains bounded as the number of qudits grows. Because the headline claim is that physical complexity scales more slowly than the proven exponential computational complexity, this gap is load-bearing.

Authors: We agree that the GRAPE-style calculations yield upper bounds on the minimal control times rather than proven global minima. The original manuscript indeed omits explicit convergence diagnostics and multiple random initializations. In the revised version we will add (i) optimization trajectories showing fidelity versus iteration count for representative cases and (ii) results from at least five independent random initializations per system size, together with the best achieved time in each case. A full landscape analysis that rigorously bounds the sub-optimality gap for growing qudit number lies beyond the scope of the present work; such an analysis remains an open problem in quantum optimal control. We will revise the text to state explicitly that the reported times are upper bounds and that the observed scaling is therefore suggestive. Even with a moderate sub-optimality factor, the contrast with the proven exponential gate-count scaling would persist, consistent with the cautious language already used in the abstract and conclusion. revision: partial

standing simulated objections not resolved

Rigorous demonstration that the true (globally optimal) physical control time scales strictly slower than exponentially with qudit number, which would require either analytical bounds or exhaustive global optimization infeasible for the dimensions considered.

Circularity Check

0 steps flagged

No significant circularity; claims rest on independent counting arguments and standard numerical optimization

full rationale

The paper derives exponential computational complexity via standard Hilbert-space dimension counting (log of the space dimension for states/unitaries), which is an external mathematical fact independent of the paper's results. Physical complexity is estimated via optimal-control-theory numerics (gradient-based pulse optimization), presented explicitly as suggestive upper-bound indications rather than fitted parameters or self-defined predictions. No self-citations, uniqueness theorems, or ansatzes from prior author work are invoked as load-bearing steps. The derivation chain does not reduce any claimed prediction to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review based solely on the abstract; no specific free parameters, axioms, or invented entities are extractable from the provided information.

pith-pipeline@v0.9.0 · 5479 in / 1051 out tokens · 117404 ms · 2026-05-11T01:45:11.460089+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

60 extracted references · 60 canonical work pages · 1 internal anchor

[1]

T. D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, and J. L. O’Brien, Quantum computers, Nature 464, 45 (2010)

work page 2010
[2]

Buluta, S

I. Buluta, S. Ashhab, and F. Nori, Natural and artificial atoms for quantum computation, Rep. Prog. Phys.74, 104401 (2011)

work page 2011
[3]

Kjaergaard, M

M. Kjaergaard, M. E. Schwartz, J. Braum¨ uller, P. Krantz, J. I-Jan Wang, S. Gustavsson, W. D. Oliver, Superconducting Qubits: Current State of Play, Annu. Rev. Condens. Matter Phys.11, 369 (2020)

work page 2020
[4]

Aruteet al., Quantum supremacy using a pro- grammable superconducting, Nature574, 505 (2019)

F. Aruteet al., Quantum supremacy using a pro- grammable superconducting, Nature574, 505 (2019)

work page 2019
[5]

Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. van den Berg, S. Rosenblatt, H. Nayfeh, Yantao Wu, M. Zaletel, K. Temme, and A. Kandala, Evidence for the utility of quantum computing before fault tolerance, Nature618, 500 (2023)

work page 2023
[6]

V. V. Sivak, A. Eickbusch, B. Royer, S. Singh, I. Tsiout- sios, S. Ganjam, A. Miano, B. L. Brock, A. Z. Ding, L. Frunzio, S. M. Girvin, R. J. Schoelkopf, and M. H. De- voret, Real-time quantum error correction beyond break- even. Nature 616, 50–55 (2023)

work page 2023
[7]

Acharyaet al., Quantum error correction below the surface code threshold, Nature638, 920 (2025)

R. Acharyaet al., Quantum error correction below the surface code threshold, Nature638, 920 (2025)

work page 2025
[8]

B. L. Brock, S. Singh, A. Eickbusch, V. V. Sivak, A. Z. Ding, L. Frunzio, S. M. Girvin, and M. H. Devoret, Quantum error correction of qudits beyond break-even, Nature641, 612 (2025)

work page 2025
[9]

E. F. Onorati, Random processes over the unitary group: mixing properties and applications in quantum informa- tion (Thesis, Freie Universit¨ at Berlin, 2019)

work page 2019
[10]

Saini, A

A. Saini, A. Tsokanos, and R. Kirner, Quantum random- ness in cryptography—a survey of cryptosystems, RNG- based ciphers, and QRNGs, Information 13.8, 358 (2022)

work page 2022
[11]

Ananth, L

P. Ananth, L. Qian, and H. Yuen, H., Cryptography from pseudorandom quantum states, in: Y. Dodis and T. Shrimpton (Eds.), Advances in Cryptology – CRYPTO 2022, Springer Nature Switzerland, 208, (2022)

work page 2022
[12]

Brown and O

W. Brown and O. Fawzi, Decoupling with random quan- tum circuits, Comm. Math. Phys.340, 867 (2015)

work page 2015
[13]

Emerson, R

J. Emerson, R. Alicki, and K. ˙Zyczkowski, Scalable noise estimation with random unitary operators, Journal of Optics B: Quantum and Semiclassical Optics7, S347 (2005)

work page 2005
[14]

P. Sen, Random measurement bases, quantum state dis- tinction and applications to the hidden subgroup prob- lem, in: 21st Annual IEEE Conference on Computational Complexity (CCC’06), 14, 287 (2006)

work page 2006
[15]

Approximation by quantum circuits.arXiv preprint quant-ph/9508006, 1995

E. Knill, Approximation by Quantum Circuits, LANL report LAUR-95-2225; arXiv:quant-ph/9508006

work page arXiv
[16]

Nakata, C

Y. Nakata, C. Hirche, M. Koashi, and A. Winter, Efficient unitary designs with nearly time-independent hamiltonian dynamics, arXiv:1609.07021

work page arXiv
[17]

S. Guo, M. Sasieta, and B. Swingle, Complexity is not enough for randomness, SciPost physics17, 151 (2024)

work page 2024
[18]

Schuster, J

T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth, Science389, 92 (2025)

work page 2025
[19]

Foxman, N

B. Foxman, N. Parham, F. Vasconcelos, and H. Yuen, Random unitaries in constant (quantum) time, arXiv:2508.11487

work page arXiv
[20]

L. Cui, T. Schuster, L. Mao, H.-Y. Huang, F. Bran- dao, Random unitaries from Hamiltonian dynamics, arXiv:2510.08434

work page arXiv
[21]

Ji, Y.-K

Z. Ji, Y.-K. Liu, and F. Song, Pseudorandom states, non- cloning theorems and quantum money, arXiv:1711.00385

work page arXiv
[22]

Y. Wang, Z. Hu, B. C. Sanders, and S. Kais, Qudits 11 and high-dimensional quantum computing, Front. Phys. 8, 479 (2020)

work page 2020
[23]

E. T. Campbell, Enhanced fault-tolerant quantum com- puting ind-level systems, Phys. Rev. Lett.113, 230501 (2014)

work page 2014
[24]

N. T. Islam, C. C. W. Lim, C. Cahall, J. Kim, and D. J. Gauthier, Provably-Secure and High-Rate Quantum Key Distribution with Time-Bin Qudits, arXiv:1709.06135 (2017)

work page arXiv 2017
[25]

Neeley, M

M. Neeley, M. Ansmann, R. C. Bialczak, M. Hofheinz, E. Lucero, A. D. O’Connell, D. Sank, H. Wang, J. Wenner, A. N. Cleland, M. R. Geller, and J. M. Martinis, Emu- lation of a quantum spin with a superconducting phase qudit, Science325, 722 (2009)

work page 2009
[26]

M. A. Yurtalan, J. Shi, M. Kononenko, A. Lupascu, and S. Ashhab, Implementation of a Walsh-Hadamard gate in a superconducting qutrit, Phys. Rev. Lett.125, 180504 (2020)

work page 2020
[27]

M. S. Blok, V. V. Ramasesh, T. Schuster, K. O’Brien, J. M. Kreikebaum, D. Dahlen, A. Morvan, B. Yoshida, N. Y. Yao, I. Siddiqi, Quantum information scrambling on a superconducting qutrit processor, Phys. Rev. X11, 021010 (2021)

work page 2021
[28]

Morvan, V

A. Morvan, V. V. Ramasesh, M. S. Blok, J. M. Kreike- baum, K. O’Brien, L. Chen, B. K. Mitchell, R. K. Naik, D. I. Santiago, and I. Siddiqi, Qutrit Randomized Bench- marking, Phys. Rev. Lett.126, 210504 (2021)

work page 2021
[29]

Kononenko, M

M. Kononenko, M. A. Yurtalan, S. Ren, J. Shi, S. Ash- hab, and A. Lupascu, Characterization of control in a superconducting qutrit using randomized benchmarking, Phys. Rev. Res.3, L042007 (2021)

work page 2021
[30]

N. Goss, A. Morvan, B. Marinelli, B. K. Mitchell, L. B. Nguyen, R. K. Naik, L. Chen, C. J¨ unger, J. M. Kreike- baum, D. I. Santiago, J. J. Wallman, and I. Siddiqi, High- fidelity qutrit entangling gates for superconducting cir- cuits, Nature Commun.13, 7481 (2022)

work page 2022
[31]

Tripathi, N

V. Tripathi, N. Goss, A. Vezvaee, L. B. Nguyen, I. Sid- diqi, and D. A. Lidar, Qudit Dynamical Decoupling on a Superconducting Quantum Processor, Phys. Rev. Lett. 134, 050601 (2025)

work page 2025
[32]

Champion, Z

E. Champion, Z. Wang, R. W. Parker, and M. S. Blok Efficient Control of a Transmon Qudit Using Effective Spin-7/2 Rotations, Phys. Rev. X15, 021096 (2025)

work page 2025
[33]

Senko, P

C. Senko, P. Richerme, J. Smith, A. Lee, I. Cohen, A. Retzker, and C. Monroe, Realization of a Quantum Integer-Spin Chain with Controllable Interactions, Phys. Rev. X5, 021026 (2015)

work page 2015
[34]

Ringbauer, M

M. Ringbauer, M. Meth, L. Postler, R. Stricker, R. Blatt, P. Schindler, and T. Monz, A universal qudit quantum processor with trapped ions, Nat. Phys.18, 1053 (2022)

work page 2022
[35]

A. S. Nikolaevaet al., Scalable Improvement of the Generalized Toffoli Gate Realization Using Trapped-Ion- Based Qutrits, Phys. Rev. Lett.135, 060601 (2025)

work page 2025
[36]

P. J. Low, N. C. Zutt, G. A. Tathed, and C. Senko, Quan- tum logic operations and algorithms in a single 25-level atomic qudit, arXiv:2507.15799

work page arXiv
[37]

X. Shi, J. Sinanan-Singh, T. J. Burke, J. Chiaverini, and I. L. Chuang, Efficient implementation of a quantum al- gorithm with a trapped ion qudit, Nat. Commun.17, 1911 (2026)

work page 1911
[38]

Fern´ andez de Fuenteset al., Navigating the 16- dimensional Hilbert space of a high-spin donor qudit with electric and magnetic fields, Nat

I. Fern´ andez de Fuenteset al., Navigating the 16- dimensional Hilbert space of a high-spin donor qudit with electric and magnetic fields, Nat. Commun.15, 1380 (2024)

work page 2024
[39]

Yuet al., Schr¨ odinger cat states of a nuclear spin qudit in silicon, Nat

X. Yuet al., Schr¨ odinger cat states of a nuclear spin qudit in silicon, Nat. Phys.21, 362 (2025)

work page 2025
[40]

Robert and T

A. Robert and T. Bienaim´ e, Qudit encoding in Rydberg blockaded arrays of atoms, arXiv:2502.06465 (2025)

work page arXiv 2025
[41]

Burshtein, S

A. Burshtein, S. Fraenkel, M. Goldstein, and R. Finkel- stein, Robust Control and Entanglement of Qudits in Neutral Atom Arrays, arXiv:2508.16294 (2025)

work page arXiv 2025
[42]

Kueset al., On-chip generation of high-dimensional entangled quantum states and their coherent control, Na- ture546, 622 (2017)

M. Kueset al., On-chip generation of high-dimensional entangled quantum states and their coherent control, Na- ture546, 622 (2017)

work page 2017
[43]

Chiet al., A programmable qudit-based quantum pro- cessor, Nat

Y. Chiet al., A programmable qudit-based quantum pro- cessor, Nat. Commun.13, 1166 (2022)

work page 2022
[44]

Basyildiz, Z

B. Basyildiz, Z. Gong, and S. Ashhab, Speed limits of two-qutrit gates, arXiv:2510.07742

work page arXiv
[45]

V. V. Shende, I. L. Markov, and S. S. Bullock, Minimal universal two-qubit controlled-NOT-based circuits, Phys. Rev. A69, 062321 (2004)

work page 2004
[46]

Plesch and C

M. Plesch and C. Brukner, Quantum-state preparation with universal gate decompositions, Phys. Rev. A83, 032302 (2011)

work page 2011
[47]

Vidal, K

G. Vidal, K. Hammerer, and J. I. Cirac, Interaction cost of nonlocal gates, Phys. Rev. Lett.88, 237902 (2002)

work page 2002
[48]

Iliat, M

A. Iliat, M. Byrd, S. Ashhab, and L.-A. Wu, Phys- ically motivated decompositions of single-qutrit gates, arXiv:2506.17797

work page arXiv
[49]

Ashhab, N

S. Ashhab, N. Yamamoto, F. Yoshihara, and K. Semba, Numerical analysis of quantum circuits for state prepa- ration and unitary operator synthesis, Phys. Rev. A106, 022426 (2022)

work page 2022
[50]

Ashhab, F

S. Ashhab, F. Yoshihara, M. Tsuji, M. Sato, and K. Semba, Quantum circuit synthesis via a random com- binatorial search, Phys. Rev. A109, 052605 (2024)

work page 2024
[51]

Zhang, J

J. Zhang, J. Vala, S. Sastry, and K. B. Whaley, Min- imum construction of two-qubit quantum operations, Phys. Rev. Lett.93, 020502 (2004)

work page 2004
[52]

Ashhab, P

S. Ashhab, P. C. de Groot, and F. Nori, Speed limits for quantum gates in multi-qubit systems, Phys. Rev. A85, 052327 (2012)

work page 2012
[53]

Khaneja, T

N. Khaneja, T. Reiss, C. Kehlet, T. S. Herbr¨ uggen, S. J. Glaser, Optimal control of coupled spin dynamics: design of NMR pulse sequences by gradient ascent algorithms, J. Magn. Reson.172, 296 (2005)

work page 2005
[54]

Ashhab F

S. Ashhab F. Yoshihara, T. Fuse, N. Yamamoto, A. Lu- pascu, and K. Semba, Speed limits for two-qubit gates with weakly anharmonic qubits, Phys. Rev. A105, 042614 (2022)

work page 2022
[55]

Basyildiz, C

B. Basyildiz, C. Jameson, and Z. Gong, Speed limits of two-qubit gates with qudits, arXiv:2312.09218

work page arXiv
[56]

Indeed, it might seem surprising that implement- ing a unitary operator on a quantum computer requires an exponentially large number of gates

This exponential scaling appears to run counter to the idea of speeding up computations using quantum com- puters. Indeed, it might seem surprising that implement- ing a unitary operator on a quantum computer requires an exponentially large number of gates. This situation raises fundamental questions about the role of RUs in quantum computation. We will n...

work page
[57]

A. C. Quillen, A. S. Miakhel, Generating pseudo-random unitaries with a Floquet driven chaotic quantum system, arXiv:2510.20581

work page arXiv
[58]

Kraus and J

B. Kraus and J. I. Cirac, Optimal creation of entangle- ment using a two-qubit gate, Phys. Rev. A63, 062309 (2001)

work page 2001
[59]

L. E. Fischer, A. Chiesa, F. Tacchino, D. J. Egger,S. Carretta, and I. Tavernelli, Universal qudit gate synthesis 12 for transmons, PRX Quantum4, 030327 (2023)

work page 2023
[60]

Reinforcement Learning for Robust Calibration of Multi-Qudit Quantum Gates

A. Jaouadi and S. Ashhab, Reinforcement learning for robust calibration of multi-qudit quantum gates, arXiv:2604.19990

work page internal anchor Pith review Pith/arXiv arXiv