nach oben

Erschienen in:

2025 | OriginalPaper | Buchkapitel

Quantum Pseudorandom Scramblers

verfasst von : Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Quantum pseudorandom state generators (PRSGs) have stimulated exciting developments in recent years. A PRSG, on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states.

In this work, we propose and construct quantum Pseudorandom State Scramblers (PRSSs), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an \(\epsilon \)-net of the state space. This significantly strengthens what standard PRSGs can induce, as they may only concentrate on a small region of the state space provided that the average output state approximates a Haar random state.

Our PRSS construction develops a parallel extension of the famous Kac’s walk, and we show that it mixes exponentially faster than the standard Kac’s walk. This constitutes the core of our proof. We also describe a few applications of PRSSs. While our PRSS construction assumes a post-quantum one-way function, PRSSs are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSGs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Real-Valued Somewhat-Pseudorandom Unitaries

More precisely, each circuit should be written as \(Q_{1^\lambda }\). Note that in a polynomial-time generated family, then \(Q_\lambda \) must have size polynomial in \(\lambda \).

Note that hiding is not required in these succinct schemes.

Aaronson, S., et al.: Quantum pseudoentanglement. In: 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 287, pp. 2:1–2:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024). https://doi.org/10.4230/LIPIcs.ITCS.2024.2

Alagic, G., Majenz, C., Russell, A.: Efficient simulation of random states and random unitaries. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 759–787. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_26CrossRef

Ananth, P., Gulati, A., Kaleoglu, F., Lin, Y.T.: Pseudorandom isometries. In: Advances in Cryptology – EUROCRYPT 2024, pp. 226–254. Springer, Cham (2024)

Ananth, P., Gulati, A., Qian, L., Yuen, H.: Pseudorandom (function-like) quantum state generators: new definitions and applications. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022, Part I, pp. 237–265. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22318-1_9

Ananth, P., Qian, L., Yuen, H.: Cryptography from pseudorandom quantum states. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part I, pp. 208–236. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15802-5_8

Behera, A., Sattath, O.: Almost public quantum coins. arXiv preprint arXiv:2002.12438 (2020)

Bouland, A., Fefferman, B., Vazirani, U.: Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality. In: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 151, pp. 63:1–63:2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.63

Brakerski, Z., Magrafta, N.: Real-valued somewhat-pseudorandom unitaries (2024)

Brakerski, Z., Shmueli, O.: (Pseudo) Random quantum states with binary phase. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11891, pp. 229–250. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36030-6_10CrossRef

10.

Brakerski, Z., Shmueli, O.: Scalable pseudorandom quantum states. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 417–440. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_15CrossRef

11.

Brandão, F.G., Chemissany, W., Hunter-Jones, N., Kueng, R., Preskill, J.: Models of quantum complexity growth. PRX Quantum 2, 030316 (2021). https://doi.org/10.1103/PRXQuantum.2.030316

12.

Brandão, F.G., Harrow, A.W., Horodecki, M.: Local random quantum circuits are approximate polynomial-designs. Commun. Math. Phys. 346, 397–434 (2016). https://doi.org/10.1007/s00220-016-2706-8

13.

Broadbent, A., González-Guillén, C.E., Schuknecht, C.: Quantum private broadcasting. Phys. Rev. A 105, 022606 (2022). https://doi.org/10.1103/PhysRevA.105.022606MathSciNetCrossRef

14.

Broadbent, A., Grilo, A.B.: QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge. SIAM J. Comput. 51(4), 1400–1450 (2022). https://doi.org/10.1137/21M140729XMathSciNetCrossRef

15.

Broadbent, A., Ji, Z., Song, F., Watrous, J.: Zero-knowledge proof systems for QMA. SIAM J. Comput. 49(2), 245–283 (2020). https://doi.org/10.1137/18M1193530MathSciNetCrossRef

16.

Chatterjee, S., Diaconis, P., Sly, A., Zhang, L.: A phase transition for repeated averages. Ann. Probab. 50(1), 1–17 (2022). https://doi.org/10.1214/21-AOP1526MathSciNetCrossRef

17.

Chen, C.F., Bouland, A., Brandão, F.G.S.L., Docter, J., Hayden, P., Xu, M.: Efficient unitary designs and pseudorandom unitaries from permutations (2024)

18.

Coladangelo, A.: Quantum trapdoor functions from classical one-way functions. arXiv preprint arXiv:2302.12821 (2023)

19.

Dankert, C., Cleve, R., Emerson, J., Livine, E.: Exact and approximate unitary \(2\)-designs and their application to fidelity estimation. Phys. Rev. A 80(1), 012304 (2009). https://doi.org/10.1103/PhysRevA.80.012304CrossRef

20.

Diaconis, P., Saloff-Coste, L.: Bounds for Kac’s master equation. Commun. Math. Phys. 209, 729–755 (2000). https://doi.org/10.1007/s002200050036MathSciNetCrossRef

21.

Gunn, S., Ju, N., Ma, F., Zhandry, M.: Commitments to quantum states. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 1579–1588. Association for Computing Machinery (2023). https://doi.org/10.1145/3564246.3585198

22.

Haferkamp, J.: Random quantum circuits are approximate unitary \(t\)-designs in depth \(O\left(nt^{5+o(1)}\right)\). Quantum 6, 795 (2022). https://doi.org/10.22331/q-2022-09-08-795

23.

Harrow, A.W., Low, R.A.: Efficient quantum tensor product expanders and k-designs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX/RANDOM -2009. LNCS, vol. 5687, pp. 548–561. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03685-9_41CrossRef

24.

Harrow, A.W., Mehraban, S.: Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates. Commun. Math. Phys. 401(2), 1531–1626 (2023). https://doi.org/10.1007/s00220-023-04675-zMathSciNetCrossRef

25.

Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97–109 (1970). https://doi.org/10.1093/biomet/57.1.97MathSciNetCrossRef

26.

Haug, T., Bharti, K., Koh, D.E.: Pseudorandom unitaries are neither real nor sparse nor noise-robust. arXiv preprint arXiv:2306.11677 (2023)

27.

Hough, B., Jiang, Y.: Cut-off phenomenon in the uniform plane Kac walk. Annals Prob. 45(4), 2248–2308 (2017). http://www.jstor.org/stable/26362254

28.

Jain, V., Pillai, N.S., Sah, A., Sawhney, M., Smith, A.: Fast and memory-optimal dimension reduction using Kac’s walk. Ann. Appl. Probab. 32(5), 4038–4064 (2022). https://doi.org/10.1214/22-AAP1784MathSciNetCrossRef

29.

Janvresse, É.: Bounds on semigroups of random rotations on \({\rm SO}(n)\). Theory Prob. Appl. 47(3), 526–532 (2003). https://doi.org/10.1137/S0040585X97979950MathSciNetCrossRef

30.

Ji, Z., Liu, Y.-K., Song, F.: Pseudorandom Quantum States. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 126–152. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_5CrossRef

31.

Jiang, Y.: Total variation bound for Kac’s random walk. In: The Annals of Applied Probability, pp. 1712–1727 (2012). https://www.jstor.org/stable/41713374

32.

Kac, M.: Foundations of kinetic theory. In: Third Berkeley symposium on mathematical statistics and probability. vol. 3, pp. 171–197 (1956)

33.

Kim, I., Tang, E., Preskill, J.: The ghost in the radiation: robust encodings of the black hole interior. J. High Energy Phys. 2020(6), 1–65 (2020). https://doi.org/10.1007/JHEP06(2020)031MathSciNetCrossRef

34.

Kretschmer, W.: Quantum pseudorandomness and classical complexity. In: 16th Conference on the Theory of Quantum Computation, Communication and Cryptography – TQC 2021, pp. 2:1–2:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.TQC.2021.2

35.

Kretschmer, W., Qian, L., Sinha, M., Tal, A.: Quantum cryptography in algorithmica. In: 55th Annual ACM Symposium on Theory of Computing (STOC 2023). pp. 1589–1602 (2023). https://doi.org/10.1145/3564246.3585225

36.

Lu, C., Qin, M., Song, F., Yao, P., Zhao, M.: Quantum pseudorandom scramblers. Cryptology ePrint Archive, Paper 2024/1470 (2024). https://eprint.iacr.org/2024/1470

37.

Metger, T., Poremba, A., Sinha, M., Yuen, H.: Simple constructions of linear-depth t-designs and pseudorandom unitaries (2024)

38.

Morimae, T., Yamakawa, T.: Quantum commitments and signatures without one-way functions. In: Advances in Cryptology – CRYPTO 2022, pp. 269–295. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15802-5_10

39.

Movassagh, R., Szegedy, M., Wang, G.: Repeated averages on graphs. arXiv:2205.04535 (2022)

40.

O’Donnell, R., Servedio, R.A., Paredes, P.: Explicit orthogonal and unitary designs. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1240–1260. IEEE Computer Society (2023). https://doi.org/10.1109/FOCS57990.2023.00073

41.

Oliveira, R.I.: On the convergence to equilibrium of Kac’s random walk on matrices. Annals Appl. Probab. 19(3), 1200–1231 (2009). https://www.jstor.org/stable/30243617

42.

Pillai, N.S., Smith, A.: Kac’s walk on \( n \)-sphere mixes in \( n\log n \) steps. Ann. Appl. Probab. 27(1), 631–650 (2017). https://doi.org/10.1214/16-AAP1214MathSciNetCrossRef

43.

Pillai, N.S., Smith, A.: On the mixing time of Kac’s walk and other high-dimensional Gibbs samplers with constraints. Annals Probab. 46(4), 2345–2399 (2018). https://www.jstor.org/stable/26506605

44.

Renes, J.M., Blume-Kohout, R., Scott, A.J., Caves, C.M.: Symmetric informationally complete quantum measurements. J. Math. Phys. 45(6), 2171–2180 (2004). https://doi.org/10.1063/1.1737053MathSciNetCrossRef

45.

Yang, L., Engelhardt, N.: The complexity of learning (pseudo)random dynamics of black holes and other chaotic systems. arXiv preprint arXiv:2302.11013 (2023)

46.

Zhandry, M.: A note on quantum-secure PRPs. Cryptology ePrint Archive, Paper 2016/1076 (2016). https://eprint.iacr.org/2016/1076

47.

Zhandry, M.: How to construct quantum random functions. J. ACM 68(5), 1–43 (2021). https://doi.org/10.1145/3450745

Titel: Quantum Pseudorandom Scramblers
verfasst von: Chuhan Lu
Minglong Qin
Fang Song
Penghui Yao
Mingnan Zhao
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-78016-5

Electronic ISBN: 978-3-031-78017-2

Copyright-Jahr: 2025
DOI: https://doi.org/10.1007/978-3-031-78017-2_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"