Parallel Kac’s Walk Generates PRU
Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao · 2025
Read Parallel Kac’s Walk Generates PRU by Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14957.txt.
Introduction
Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao wrote this paper in two thousand twenty-five. It shows that a row of parallel Kac's walk steps forms a pseudorandom unitary family with strong security.
Pseudorandom unitaries act like true random ones to any bounded test, and are a base tool in quantum crypto. A prior build, the PFC construction, was lately shown secure by a path recording proof. The authors prove the same for their walk-based build, settling a guess from their own past work. Their version also stands up to foes that can run the unitaries backward. The result gives a second route to the same strong tool.
Catalog record
| CREATOR | Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 234 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-14957
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Parallel Kac’s Walk Generates PRU Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao Abstract Ma and Huang recently proved that the PFC construction, introduced by Metger, Poremba, Sinha and Yuen [ 24 ] , gives an adaptive-secure pseudorandom unitary family (PRU). Their proof developed a new path recording technique [ 22 ] . In this work, we show that a linear number of sequential repetitions of the parallel Kac’s Walk , introduced by Lu, Qin, Song, Yao and Zhao [ 21 ] , also forms an adaptive-secure PRU , confirming a conjecture therein. Moreover, it additionally satisfies strong security against adversaries making inverse queries. This gives an alternative PRU construction, and provides another instance demonstrating the power of the path recording technique. We also discuss some further simplifications and implications. 1 Introduction Pseudorandomness is a fundamental concept in cryptography. The basic pseudorandom objects, including pseudorandom functions ( PRF s), pseudorandom permutations ( PRP s) and pseudorandom generators ( PRG s), have served as primitives in modern classical cryptography. Pseudorandom objects in quantum information have witnessed increasing influences in recent years. The first example is pseudorandom states ( PRS s), introduced by Ji, Liu and Song [ 19 ] , which are a set of states that can be prepared by polynomial-sized quantum circuits and look indistinguishable from Haar random states for any polynomial-time quantum distinguisher. They gave the first construction of PRS s. PRS s have found applications in various areas including quantum cryptography [ 3 ] , quantum learning theory [ 14 ] and quantum gravity [ 5 , 31 ] . Since their work, a number of different constructions have been discovered [ 7 , 12 , 18 , 6 ] . Ji, Liu and Song further introduced the concept of pseudorandom unitaries ( PRU s), which are ensembles of unitaries that are efficient to implement, but are indistinguishable from Haar random unitaries by any quantum polynomial-time distinguisher. The construction of PRU turns out to be challenging and a large body of work has been devoted to constructing pseudorandom objects that partially realize PRU ’s functions. Examples include scalable pseudorandom states [ 8 ] , pseudorandom function-like quantum state generators [ 2 ] , pseudorandom isometries [ 1 ] , and pseudorandom scramblers [ 21 ] . A giant leap was achieved by Metger, Poremba, Sinha and Yuen [ 24 ] where a pseudorandom unitary family is constructed against non-adaptive adversaries. Their construction is a PFC ensemble, where the circuits sequentially apply a uniformly random Clifford gate, a diagonal unitary with a (pseudorandom) random phase f:\left\{0,1\right\}^{n}\rightarrow\left\{-1,1\right\} , and then a (pseudorandom) permutation matrix on n -qubit computational basis states. Soon after, Ma and Huang in their very recent work [ 22 ] proved that PFC ensembles are indeed secure against adaptive adversaries as well, provably establishing the feasibility of PRU for the first time. 1.1 Main result In this work, we carry on the exciting advancement on PRU lately. We show that the parallel Kac’s walk construction, introduced in [ 21 ] , also produces an adaptive-secure PRU . The original Kac’s walk , introduced by Kac [ 20 ] in 1956, is a random walk on unitary groups, which has been extensively studied by mathematical physicists. Kac’s walk has also found applications in the construction of polynomial designs [ 9 ] and memory-optimal dimension reduction [ 15 ] . To put it in the language of quantum computing, in one step of Kac’s walk, the algorithm randomly selects two elements of the computational basis \left\{\ket{i},\ket{j}\right\} and implements a random 2\times 2 unitary in the space spanned by these two basis elements. Kac’s walk can also be viewed as a random walk on a unit sphere, where all the random unitaries sampled by the walk are applied to an initial unit vector sequentially. Pillai and Smith [ 26 ] showed a tight \Theta(N\log N) mixing time for Kac’s walk on an N -dimensional unit sphere. Lu, Qin, Song, Yao and Zhao [ 21 ] introduced a variant called parallel Kac’s walk . It randomly samples a random matching among all N computational basis elements, say \left\{\left(\ket{i_{1}},\ket{j_{1}}\right),\ldots,\left(\ket{i_{N/2}},\ket{j_{N/2}}\right)\right\} , which is done in a single step via a random permutation of all basis elements. For each pair \left(\ket{i},\ket{j}\right) , the algorithm implements a 2\times 2 Haar random unitary. By replacing the random functions and random permutations with their quantum-secure pseudorandom counterparts, one obtains an efficient implementation of one step of the parallel Kac’s walk. It was shown that a parallel Kac’s walk reduces the mixing time by a factor N . Consequently, O(\log N) steps of parallel Kac’s walk, which is linear in the number of qubits n , map any input pure state to a (pseudo)random state. This is formalized as a primitive called ( pseudo ) random state scrambler in [ 21 ] . It was left open in their paper whether such a construction can generate a PRU . In this paper, we show an affirmative answer that linear steps of parallel Kac’s walk indeed form a PRU . Theorem 1.1 (Main Theorem, Informal) The distribution of the unitary corresponding to an O(n) -step random parallel Kac’s walk is computationally indistinguishable from Haar distribution against adaptive adversaries. Moreover, without asymptotically increasing the number of steps, it also remains secure against adversaries capable of making inverse queries. Proof overview. The proof comprises two phases. First we show that O(n) iterations of parallel Kac’s walk effectively project the adversary’s state to what we term the distinct block subspace . We divide \{0,1\}^{n} into N/2 blocks, each containing two bit strings. We define (x_{1},\dots,x_{t})\in(\{0,1\}^{n})^{t} to be in the distinct block subspace if they belong to different blocks. Once the state is promised to reside in the distinct block subspace, the second phase employs a single step of parallel Kac’s walk to ensure that the entire construction is indistinguishable from a Haar random unitary. More specifically, in the initial phase, we leverage the random state scrambling property of parallel Kac’s walk as introduced in [ 21 ] to ensure that the adversary’s state is approximately in the distinct subspace after O(n) steps. To further show the projection into the distinct block subspace, imagine inserting an additional random permutation that does not affect the construction (since every iteration inherently includes a random permutation). Given that the adversary’s state already resides in the distinct subspace, applying a random permutation will cause it to fall into the distinct block subspace with high probability. Note that 2-designs, such as random Clifford, can also project states onto distinct block subspaces. However, parallel Kac’s walk alone is not known to form a 2-design, and hence this does not help us build a PRU purely based on the parallel Kac’s walk. Therefore, we instead directly prove that the parallel Kac’s walk suffices for this purpose by an unexpected application of a random scrambling property established in [ 21 ] . In the second phase, we adapt the techniques in [ 22 ] . A key ingredient in their method is the path-recording oracle of [ 22 ] , which was designed so that it behaves indistinguishably from both the (purified) \mathsf{PF} and Haar random distribution as