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

arXiv:2605.07374 · quant-ph · Submitted 2026-05-08 · 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: We're looking at the paper: "Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators".

Mira: Here's the gist of the paper. Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators analyzes the complexity of synthesizing random states and unitary operators in a multi-qudit system in two paradigms.

Kai: The computational complexity of random states or unitary operators scales exponentially with the number of qudits, while the physical complexity scales more slowly.

Mira: Complexity Paradigms The analysis considers two paradigms for synthesizing quantum states and unitary operators.

Kai: The first paradigm involves manipulating the system by applying a sequence of one- and two-qudit quantum gates that constitute the elementary, and universal, gate set.

Paper summary: Kai: So to recap, this paper, "Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators," looks at the complexity in two ways: computational gates versus physical time. The main point is that the computational complexity scales exponentially with the number of qudits, but the physical complexity scales much slower.

Mira: The paper argues that this difference is important because it shows that even if we can't synthesize these things perfectly, there are always pseudorandom versions available using a polynomial number of gates.

Lev: That means the hardware doesn't necessarily need to achieve an exponential gate count to get close enough to a random operator.

Kai: The paper also gives specific scaling laws for state preparation and unitary synthesis based on the number of qudits, like N being related to (2n - one - n)/two for state preparation <ref:2605.07374#pg1>.

Mira: And they also give a formula for unitary operator synthesis, N = (4n - one - 3n)/four which relates the number of CZ gates needed to synthesize an arbitrary target <ref:2605.07374#pg1>.

Lev: Those formulas are nice because they give us concrete lower bounds, but we have to remember these are based on using only single-qudit and two-qudit entangling gates.

Kai: The paper also touches on how the physical complexity is defined as the minimum time needed for state preparation and unitary operator synthesis using optimal control theory calculations.

Mira: And they show that this physical time scaling is different from the computational gate counting scaling, showing a slower dependence on n and d for state preparation.

Lev: From an engineering perspective, that slower scaling for state preparation suggests that preparing states in larger systems might be less time-consuming than the exponential gate count would imply.

Kai: They also analyze random versus pseudorandom ensembles to show that PRUs scale polynomially with the number of qudits because they can be synthesized with a polynomial or even logarithmic number of elementary gates.

Mira: And they reinforce that there’s always an arbitrarily close random unitary operator available, and the time to reach it is infinitesimally close to the time needed for state preparation.

Lev: So, if we can get those PRUs efficiently computationally, we don't need a huge physical time penalty for the actual synthesis of a truly random one.

Kai: And they also detail how they justify their fidelity threshold of zero point nine nine nine as the minimum gate time in a fully controllable system.

Mira: That minimum gate time is derived by projecting the target unitary operator onto spaces spanned by different terms in the Hamiltonian and taking inverse powers of those projected norms.

Lev: So, we have a concrete way to calculate that time, even if it’s based on some ideal assumptions about our control system.

Kai: The paper also discusses how parameter counting leads to limitations on expressing the operator simply when you have more qudits or higher levels per qudit than two.

Mira: This means the structure of the operator is inherently more complicated than a simple sum of basic building blocks when n and d get larger, which makes decomposition hard.

Lev: That’s a structural limitation we need to keep in mind for scaling up our experimental control schemes.

Conclusion: Kai: So looking at this paper, "Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators," it really boils down to the idea that complexity isn't just about how many gates or how long it takes to get a result.

Mira: It shows that for multi-qudit systems, the computational cost explodes exponentially with system size, but the physical time cost doesn't follow that same steep curve.

Lev: The authors are providing mathematical lower bounds for gate counts and then showing how those bounds hold up against numerical calculations in small systems.

Kai: The main implication is that we have guiding rules for controlling and utilizing these multi-qudit systems based on the scaling laws they found, which help us figure out what to expect when we build bigger machines.

Mira: It suggests that for generating random states, pseudorandom versions are computationally easier to achieve than truly random ones, and the physical time cost remains manageable.

Lev: So, if we can get those pseudorandom states efficiently with gates, the physical time penalty isn't as bad as the paper’s initial complexity estimates suggested.

Kai: The paper is a deep look at how gate counts translate into real-world constraints for controlling these multi-qudit setups.

Mira: It gives us a clearer picture of the relationship between these two types of complexity, which helps us decide where to focus our research next in this area.

Advanced ICT Research Institute · Research Institute for Science and Technology, Tokyo University of Science · California Institute of Technology

quant-ph

Submitted: 2026-05-08

Updated: 2026-11-05

Comments: 12 pages, 2 tables

Journal ref: Phys. Rev. A 114, 052412 (2026)

DOI: 10.1103/hpzl-bg8d

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

Importance score: 90/100

The gist: Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators analyzes the complexity of synthesizing random states and unitary operators in a…

Key concepts

Computational Complexity
This measures the minimum number of basic quantum gates needed to achieve a desired state or operator. The analysis shows this required gate count grows exponentially as the system size (number of qudits) increases, setting a hard limit on how efficiently we can compute these operations.
Physical Complexity
This measures the minimum time required to perform an operation using optimal physical control pulses. For state preparation, this time is weakly dependent on system size. However, synthesizing a unitary operator shows a stronger dependence, increasing by about a factor of 8 when moving from two to three qudits.
Random vs. Pseudorandom Ensembles
The paper suggests that physical complexity for pseudorandom unitaries is at most polynomial because they can be made with relatively few gates. Furthermore, any truly random unitary operator can be approximated arbitrarily closely by a pseudorandom one, meaning the time to synthesize them is nearly identical.
Hamiltonian Dynamics/Control
The physical synthesis time estimate relies on projecting the target unitary onto spaces spanned by Hamiltonian terms and using inverse powers of their norms. This method helps determine the minimum operation time needed when using optimal control theory to drive the physical system.

Terminology

Summary

Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators analyzes the complexity of synthesizing random states and unitary operators in a multi-qudit system in two paradigms. p. 0 The computational complexity of random states or unitary operators scales exponentially with the number of qudits, while the physical complexity scales more slowly. p. 0

Complexity Paradigms

The analysis considers two paradigms for synthesizing quantum states and unitary operators. The first paradigm involves manipulating the system by applying a sequence of one- and two-qudit quantum gates that constitute the elementary, and universal, gate set. p. 0 The second paradigm manipulates the physical system using physical fields with optimized control pulses. p. 1

Computational Complexity Analysis

The computational complexity is defined by the minimum number of elementary quantum gates required to perform the desired operation. Lower bounds for synthesizing an n-qubit RS or RU using the two-qubit CZ gate as the entangling gate are derived based on counting adjustable parameters and comparing them with independent parameters in the target state or operator. p. 1 The numerical results show that the circuit size lower bound clearly scales exponentially with the number of qudits. p. 2

Physical Complexity Analysis

The physical complexity is defined by the minimum time required to perform the desired operation using optimal control theory calculations. The minimum operation time for state preparation and unitary operator synthesis shows different scaling behaviors compared to computational complexity. p. 5 For state preparation, the operation time is only weakly dependent on n and d. p. 5 For unitary operator synthesis, the operation time increases with increasing n by a factor of about 8 for qutrits (d=3) when moving from n=2 to n=3. p. 5

Random vs. Pseudorandom Ensembles

The results imply that the physical complexity of synthesizing PRUs scales at most polynomially with the number of qudits because PRUs can be synthesized with a polynomial or logarithmic number of elementary gates. Furthermore, there must exist arbitrarily close RUs to any PRU. p. 5 The time needed to synthesize an infinitesimally close RU to a PRU is infinitesimally close to the time needed to prepare the PRU. p. 6

Physical Justification and Speed Limits

The numerical threshold of fidelity F = 0.999 is justified for identifying the minimum gate time in a fully controllable system. p. 7 The synthesis time estimate is derived by projecting the target unitary operator onto spaces spanned by different terms in the Hamiltonian and taking inverse powers of the projected norms. p. 7 The resulting synthesis time estimate is proportional to 1/K where K depends on the number of commutators needed to access all directions. p. 6

Physical Complexity Bounds Based on Parameter Counting

A parameter counting procedure suggests that for a general n-qudit unitary operator Uˆ, Aˆ must have d squared + 2n - 1 free parameters. This leads to the conclusion that Aˆ cannot be expressed as the sum of only single-qubit and two-qudit terms for n > 2 and/or d > 2. p. 8 The parameter counts quickly become large, making a straightforward decomposition difficult. p. 8

Alternative Physical Settings

The work considered a specific form of the Hamiltonian using interqudit coupling terms corresponding to a bi-linear interaction between harmonic oscillators, motivated by superconducting qudits. The assumption that different qudit transitions can be driven independently is made for theoretical study, although this generalization slows down pulse optimization calculations. p. 4 The choice of Hamiltonian is consistent with similar assumptions made when analyzing computational complexity. p. 4

Computation Time

The computation time for the numerical optimizations took times ranging from a few hours to a few days per optimization. The computation time is not strongly correlated with the physical evolution time, meaning calculating optimal pulses can take a long calculation time even if the operation time is small. p. 9 The minimum operation time decreases even though the Hilbert space size increases for two-qubit state preparation. p. 9

Conclusion

The analysis derived mathematical lower bounds for gate counts and verified them with numerical calculations. The study provided insight into how the physical complexity scales for synthesizing RSs and RUs. p. 9 The results offer guiding rules for future work on controlling and utilizing multi-qudit systems. p. 9

Acknowledgments

SA acknowledges the support from Japan’s Ministry of Education, Culture, Sports, Science and Technology (MEXT) Quantum Leap Flagship Program Grant Number JPMXS0120319794. BB acknowledges funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY2317110). p. 9

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

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

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

[4] F. Arute et al. p. 9, Quantum supremacy using a programmable superconducting, Nature 574, 505 (2019). p. 9

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

[6] V. V. Sivak, A. Eickbusch, B. p. 9 Royer, S. Singh, I. Tsioutsios, S. p. 9 Ganjam, A Miano, B L Brock A Z Ding L Frunzio S M Girvin R J Schoelkopf and M H Devoret Real-time quantum error correction beyond breakeven Nature 616 50–55 (2023). p. 9

[7] R. Acharya et al. p. 9, Quantum error correction below the surface code threshold Nature 638 920 (2025). p. 9

[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 Nature 641 612 (2025). p. 9

[9] E F Onorati Random processes over the unitary group mixing properties and applications in quantum information Thesis Freie Universitat Berlin 2019. p. 9

[10] A Saini A Tsokanos and R Kirner Quantum randomness in cryptography a survey of cryptosystems RNGbased ciphers and QRNGs Information 13. p. 98 358 (2022). p. 9

[11] P Ananth L Qian and H Yuen H Cryptography from pseudorandom quantum states in Advances in Cryptology CRYPTO 2022 Springer Nature Switzerland 208 (2022). p. 9

[12] W Brown and O Fawzi Decoupling with random quantum circuits Comm Math Phys 340 867 (2015). p. 9

[13] J Emerson R Alicki, and K Zyczkowski Scalable noise estimation with random unitary operators Journal of Optics B Quantum and Semiclassical Optics 7 S347 (2005). p. 9

[14] P Sen Random measurement bases quantum state distinction and applications to the hidden subgroup problem in 21st Annual IEEE Conference on Computational Complexity CCC’06 14 287 (2006). p. 9

[15] E Knill Approximation by Quantum Circuits LANL report LAUR-95-2225 arXiv:quant-ph/9508006. p. 9

[16] Y Nakata C Hirche M Koashi and A Winter Efficient unitary designs with nearly time independent hamiltonian dynamics arXiv:1609. p. 907021.

[17] S Guo M Sasieta and B Swingle Complexity is not enough for randomness SciPost physics 17 151 (2024). p. 9

[18] T Schuster J Haferkamp and H Y Huang Random unitaries in extremely low depth Science 389 92 (2025). p. 9

[19] B Foxman N Parham F Vasconcelos and H Yuen Random unitaries in constant quantum time arXiv:2508. p. 911487.

[20] L Cui T Schuster L Mao H Y Huang F Brandao Random unitaries from Hamiltonian dynamics arXiv:2510. p. 908434.

[21] Z Ji Y K Liu and F Song Pseudorandom states noncloning theorems and quantum money arXiv:1711. p. 900385.

[22] Y Wang Z Hu B C Sanders and S Kais Qudits Front Phys 8 479 (2020). p. 9

[23] E T Campbell Enhanced fault-tolerant quantum computing in d-level systems Phys Rev Lett 113 230501 (2014). p. 9

[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.

[25] 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 Martinis Emulation of a quantum spin with a superconducting phase qudit Science 325 722 (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). p. 9

[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 X 11 021010 (2021).

[28] A Morvan V V Ramasesh M S Blok J M Kreikebaum K O’Brien L Chen B K Mitchell R K Naik D I Santiago and I Siddiqi Qutrit Randomized Benchmarking Phys Rev Lett 126 210504 (2021).

[29] M Kononenko M A Yurtalan S Ren J Shi S Ashhab and A Lupascu Characterization of control in a superconducting qutrit using randomized benchmarking Phys Rev Res 3 L042007 (2021).

[30] N Goss A Morvan B Marinelli B K Mitchell L B Nguyen R K Naik L Chen C Jüngger J M Kreikebaum D I Santiago J J Wallman and I Siddiqi Highfidelity qutrit entangling gates for superconducting circuits Nature Commun 13 7481 (2022). p. 0

[31] V Tripathi N Goss A Vezvaee L B Nguyen I Siddiqi and D A Lidar Qudit Dynamical Decoupling on a Superconducting Quantum Processor Phys Rev Lett 134 050601 (2025).

[32] 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 X 15 021096 (2025).

[33] 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 X 5 021026 (2015).

[34] 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). p. 0

[35] A S Nikolaeva et al Scalable Improvement of the Generalized Toffoli Gate Realization Using Trapped-IonBased Qutrits Phys Rev Lett 135 060601 (2025).

[36] P J Low N C Zutt G A Tathed and C Senko Quantum logic operations and algorithms in a single 25-level atomic qudit arXiv:2507. p. 015799.

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

[38] I Fern´andez de Fuentes et al Navigating the 16-dimensional Hilbert space of a high-spin donor qudit with electric and magnetic fields Nat Commun 15 1380 (2024). p. 7

[39] X Yu et al Schr¨odinger cat states of a nuclear spin qudit in silicon Nat Phys 21 362 (2025). p. 0

[40] A Robert and T Bienaim´e Qudit encoding in Rydberg blockaded arrays of atoms arXiv:2502. p. 006465.

[41] A Burshtein S Fraenkel M Goldstein and R Finkelstein Robust Control and Entanglement of Qudits in Neutral Atom Arrays arXiv:2508. p. 916294.

[42] M Kues et al On-chip generation of high-dimensional entangled quantum states and their coherent control Nature 546 622 (2017). p. 5

[43] Y Chi et al A programmable qudit-based quantum processor Nat Commun 13 1166 (2022). p. 0

[44] B Basyildiz Z Gong and S Ashhab Speed limits of two-qutrit gates arXiv:2510. p. 907742.

[45] V V Shende I L Markov and S S Bullock Minimal universal two-qubit controlled-NOT-based circuits Phys Rev A 69 062321 (2004). p. 0

[46] M Plesch and C Brukner Quantum-state preparation with universal gate decompositions Phys Rev A 83 032302 (2011). p. 2

[47] G Vidal K Hammerer and J I Cirac Interaction cost of nonlocal gates Phys Rev Lett 88 237902 (2002). p. 4

[48] A Iliat M Byrd S Ashhab and L-A Wu Physically motivated decompositions of single-qutrit gates arXiv:2506.17797.

[49] S Ashhab N Yamamoto F Yoshihara and K Semba Numerical analysis of quantum circuits for state preparation and unitary operator synthesis Phys Rev A 106 022426 (2022). p. 2

[50] S Ashhab F Yoshihara M Tsuji M Sato and K Semba Quantum circuit synthesis via a random combinatorial search Phys Rev A 109 052605 (2024).

[51] J Zhang J Vala S Sastry and K B Whaley Minimum construction of two-qubit quantum operations Phys Rev Lett 93 020502 (2004). p. 5

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved understanding of complexity scaling for random states and unitary operators in multi-qudit systems by distinguishing between computational complexity (number of gates) and physical complexity (minimum time). This allows researchers to predict whether a desired operation is more limited by the required circuit size or the physical time needed for control pulses.

  2. Development of tighter lower bounds for two-qudit CZ gate counts in qudits, such as NS = 2times d n - 2 - d(d - 1)n / (2d(d - 1)), which helps in benchmarking and verifying the performance limits of specific entangling gates.

  3. Ability to estimate minimum synthesis times for random quantum operations by using a recipe based on projections of the target unitary operator onto subspaces spanned by Hamiltonian terms, providing an estimate proportional to epsilon G(k) / H.

  4. Prediction that the physical complexity of synthesizing pseudorandom unitary operators scales at most polynomially with the number of qudits, based on the conjecture that if PRUs can be synthesized with a polynomial number of gates, their continuous-time synthesis time will also scale polynomially.

  5. Enhanced design of quantum control pulses by recognizing that for unitary operator synthesis, it is better to achieve dynamics with a single repetition of the gate sequence and as large steps as possible rather than cutting the sequence into short time steps to follow the geodesic.

Sources

Related papers