Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators
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 analytically that the computational complexity of synthesizing random states or unitary operators scales exponentially with the number of qudits. While our numerical results are limited to small systems and are insufficient to reveal the asymptotic scaling laws, they suggest that the physical complexity of synthesizing 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.
Versions
Related
- Logic, Information, Holography: A Recursive Unification of Complexity Across Computational, Physical, and Geometric Substrates
- From Analytic Structure to Quantum Complexity: Walsh-Pauli Representations of Continuum Operators
- Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
- On the Computational Complexity of Blind Quantum Machine Learning
- Spacetime Quasicrystals and Computational Complexity Theory in the Road Towards Quantum Gravity
BibTeX
@misc{ashhab2026computational,
title = {{Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators}},
author = {Sahel Ashhab and Bora Basyildiz},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.07374},
eprint = {2605.07374},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.07374},
}
RIS
TY - UNPB
TI - Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators
AU - Sahel Ashhab
AU - Bora Basyildiz
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2605.07374
UR - https://arxiv.org/abs/2605.07374
AB - 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 analytically that the computational complexity of synthesizing random states or unitary operators scales exponentially with the number of qudits. While our numerical results are limited to small systems and are insufficient to reveal the asymptotic scaling laws, they suggest that the physical complexity of synthesizing 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.
ER -