# (Pseudo) Random Quantum States with Binary Phase

arXiv: https://arxiv.org/abs/1906.10611 · HTML: https://mlsanity.com/paper/1906.10611/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2019.

## Built on by (most cited first, 10 of 10)

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates](https://mlsanity.com/paper/2305.13409/) (2023)
- [Certifying almost all quantum states with few single-qubit measurements](https://mlsanity.com/paper/2404.07281/) (2024)
- [Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom](https://mlsanity.com/paper/2209.14530/) (2022)
- [When can classical neural networks represent quantum states?](https://mlsanity.com/paper/2410.23152/) (2024)
- [Quantum Topological Data Analysis with Linear Depth and Exponential Speedup](https://mlsanity.com/paper/2108.02811/) (2021)
- [Topological data analysis on noisy quantum computers](https://mlsanity.com/paper/2209.09371/) (2022)
- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)
- [Quantum Solutions to the Privacy vs. Utility Tradeoff](https://mlsanity.com/paper/2307.03118/) (2023)
- [Unclonability and Quantum Cryptanalysis: From Foundations to Applications](https://mlsanity.com/paper/2210.17545/) (2022)

## Abstract (arXiv)

We prove a quantum information-theoretic conjecture due to Ji, Liu and Song (CRYPTO 2018) which suggested that a uniform superposition with random binary phase is statistically indistinguishable from a Haar random state. That is, any polynomial number of copies of the aforementioned state is within exponentially small trace distance from the same number of copies of a Haar random state. As a consequence, we get a provable elementary construction of pseudorandom quantum states from post-quantum pseudorandom functions. Generating pseduorandom quantum states is desirable for physical applications as well as for computational tasks such as quantum money. We observe that replacing the pseudorandom function with a (2t)-wise independent function (either in our construction or in previous work), results in an explicit construction for quantum state t-designs for all t. In fact, we show that the circuit complexity (in terms of both circuit size and depth) of constructing t-designs is bounded by that of (2t)-wise independent functions. Explicitly, while in prior literature t-designs required linear depth (for t > 2), this observation shows that polylogarithmic depth suffices for all t. We note that our constructions yield pseudorandom states and state designs with only real-valued amplitudes, which was not previously known. Furthermore, generating these states require quantum circuit of restricted form: applying one layer of Hadamard gates, followed by a sequence of Toffoli gates. This structure may be useful for efficiency and simplicity of implementation.