We construct a quantum oracle relative to which BQP = QMA but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if BQP = PP. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
We construct a quantum oracle relative to which BQP = QMA but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if BQP = PP. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that P ≠ N P , which gives a lower bound on the necessary hardness.One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.We show that pseudorandom states compressing n bits to log n + 1 qubits can be used to build one-way state generators and pseudorandom states compressing n bits to ω ( log n ) qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than c log n -qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a P P oracle.An interesting implication of our results is that a t ( n ) -copy one-way state generator exists unconditionally, for every t ( n ) = o ( n / log n ) . This contrasts nicely with the previously known fact that O ( n ) -copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments.
There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs) and quantum-computable PRGs. Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relations among quantum pseudorandomness have yet to be fully established. We present evidence suggesting that some forms of quantum pseudorandomness are unlikely to be constructed from the others. This indicates that quantum pseudorandomness behaves quite differently from classical pseudorandomness. Our main result is a unitary oracle separation where log-length output PRFSGs exist but quantum-computable pseudorandom generators (QPRGs) with negligible correctness error do not. This result suggests that the inverse-polynomial error in the state-of-the-art construction of QPRGs from log-length PRSGs is inherent. To achieve this, we prove a novel differential geometric barrier theorem for the product Haar measure on quantum states which replaces the usual concentration inequalities by certifying a non-negligible ``gap'' between two large trace-separated sets. Our separation is based on an oracle that outputs Haar random quantum states for each bit string, which can be viewed as a quantum version of the random oracle model, where output strings are replaced by quantum states. Variations of this oracle can be used to study other relationships between quantum cryptographic primitives, and we use it to achieve partial separations, that highlight technical difficulties when dealing with ancillary registers, measurements, and adaptivity in the quantum setting.
We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRSs) with superlogarithmic output length do not. At first glance, this appears to contradict the known black-box constructions of PRS generators from quantum-secure OWFs. The distinction lies in the access model to the oracles; our oracle separation uses \emph{classical-accessible} random oracles that can be accessed only classically even by quantum algorithms. In fact, our impossibility of PRSs applies to \emph{any} classically accessible classical oracle in place of the random oracle, while keeping the other oracle component unchanged, showing the need for coherent access in constructing PRSs.
We further show that logarithmic output length pseudorandom function-like states (PRFSs) exist relative to our oracles, giving an oracle separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs. This shows that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS.
Quantum pseudorandomness is an emerging research area. Ji, Liu, and Song defined pseudorandom states (PRSs) and pseudorandom unitaries (PRUs) as quantum analogs of pseudorandom generators and pseudorandom functions. A unitary oracle separation result between one-way functions and PRSs/PRUs, established by Kretschmer, suggests that certain quantum primitives may remain secure even if classical cryptography is compromised. This insight has spurred extensive work on quantum pseudorandomness and its applications in quantum cryptography. Many constructions of PRSs have been established under standard assumptions, yet building a secure PRU was a long-standing open problem. This dissertation aims to narrow the gap between PRSs and PRUs and presents results that go beyond PRSs. We introduce Pseudorandom State Scramblers (PRSSs), a new primitive that lies between PRSs and PRUs. A PRSS maps any pure state to a pseudorandom state, a property shared with PRUs but not with PRSs. We present a construction of PRSSs inspired by the well-known Kac’s walk, and in particular, we develop a parallel variant that significantly accelerates the mixing time, enabling an efficient construction. PRSSs support cryptographic tasks not known to be achievable from PRSs alone, including a quantum encryption scheme and a succinct quantum state commitment. Additionally, when suitable classical randomness is provided, our construction exhibits a special dispersing property not known to be satisfied by any existing construction of quantum pseudorandom primitives. Our subsequent work shows that, without asymptotically increasing the number of steps, our construction based on the parallel Kac’s walk yields PRUs with standard or even strong security. The proof builds on a recently developed technique for establishing adaptive security, known as the path-recording method. This result provides an alternative construction of PRUs and further showcases the power of this proof technique. In addition, this dissertation includes two side projects. The first revisits the Hidden Subgroup Problem over ℤn, providing a simplified analysis of a known quantum algorithm using elementary lattice tools. The second establishes a quantum analogue of a classical impossibility result for statistical non-interactive zero-knowledge arguments, showing limitations of black-box reductions under classical-query quantum adversaries.
We construct a classical oracle relative to which P = NP yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo’s five worlds, this is a construction of pseudorandom states in ”Algorithmica,” and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle, and (3) is independent of P vs. NP in the black-box setting. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states.
The relationship between efficient verification and quantum computing is one of the most important and least well-understood questions in the theory of computation. In particular, is there a problem that can be solved efficiently on a quantum computer that cannot be verified? In this thesis we give evidence that BQP ⊄ PH, relating the classes of languages decidable with a quantum computer to a generalization of NP. In so doing we connect a question in pseudorandomness, first studied [BSW03] to the problem of finding an oracle relative to which BQP ⊄ PH. The primary technical challenge is to construct a unitary matrix, realized by an efficient quantum circuit and whose rows are supported on nearly disjoint subsets. Using this matrix and assuming the validity of the aforementioned question in pseudorandomness, we show an instantiation of the Nisan-Wigderson pseudorandom generator that can be broken with quantum computers, but not with the relevant mode of classical computation.