Pseudorandom unitaries are neither real nor sparse nor noise-robust
Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist o...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-06-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-06-04-1759/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850233845451849728 |
|---|---|
| author | Tobias Haug Kishor Bharti Dax Enshan Koh |
| author_facet | Tobias Haug Kishor Bharti Dax Enshan Koh |
| author_sort | Tobias Haug |
| collection | DOAJ |
| description | Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Further, we show an exponential advantage in imaginarity testing when having access to the complex conjugate of the state. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness. |
| format | Article |
| id | doaj-art-8cbe0e42f67644f680a9052f148aee98 |
| institution | OA Journals |
| issn | 2521-327X |
| language | English |
| publishDate | 2025-06-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj-art-8cbe0e42f67644f680a9052f148aee982025-08-20T02:02:48ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2025-06-019175910.22331/q-2025-06-04-175910.22331/q-2025-06-04-1759Pseudorandom unitaries are neither real nor sparse nor noise-robustTobias HaugKishor BhartiDax Enshan KohPseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Further, we show an exponential advantage in imaginarity testing when having access to the complex conjugate of the state. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.https://quantum-journal.org/papers/q-2025-06-04-1759/pdf/ |
| spellingShingle | Tobias Haug Kishor Bharti Dax Enshan Koh Pseudorandom unitaries are neither real nor sparse nor noise-robust Quantum |
| title | Pseudorandom unitaries are neither real nor sparse nor noise-robust |
| title_full | Pseudorandom unitaries are neither real nor sparse nor noise-robust |
| title_fullStr | Pseudorandom unitaries are neither real nor sparse nor noise-robust |
| title_full_unstemmed | Pseudorandom unitaries are neither real nor sparse nor noise-robust |
| title_short | Pseudorandom unitaries are neither real nor sparse nor noise-robust |
| title_sort | pseudorandom unitaries are neither real nor sparse nor noise robust |
| url | https://quantum-journal.org/papers/q-2025-06-04-1759/pdf/ |
| work_keys_str_mv | AT tobiashaug pseudorandomunitariesareneitherrealnorsparsenornoiserobust AT kishorbharti pseudorandomunitariesareneitherrealnorsparsenornoiserobust AT daxenshankoh pseudorandomunitariesareneitherrealnorsparsenornoiserobust |