Lattice-Based Quantum Advantage from Rotated Measurements

Yusuf Alnawakhtha; Atul Mantri; Carl A. Miller; Daochen Wang

doi:10.22331/q-2024-07-04-1399

Lattice-Based Quantum Advantage from Rotated Measurements

Yusuf Alnawakhtha¹, Atul Mantri^1,2, Carl A. Miller^1,3, and Daochen Wang^1,4

¹Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742, USA
²Department of Computer Science, Virginia Tech, Blacksburg, VA 24060, USA
³Computer Security Division, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA
⁴Department of Computer Science, University of British Columbia, Vancouver, V6T 1Z4, Canada

Published:	2024-07-04, volume 8, page 1399
Eprint:	arXiv:2210.10143v3
Doi:	https://doi.org/10.22331/q-2024-07-04-1399
Citation:	Quantum 8, 1399 (2024).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli-$X$ or $Z$ measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the $XY$-plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the $XY$-plane up to a Pauli-$Z$ correction.

Featured image: Example of the phase picked up on a "claw-state" when performing a single-qubit rotation.

Popular summary

A proof of quantumness is a protocol that is difficult for classical devices to perform but easy for a quantum device. It is desirable for such protocols to be implementable on simple quantum devices while still being secure against classical devices with as few computational restrictions as possible. In this work, we design a two-round proof of quantumness protocol based on standard post-quantum hardness assumptions which combines different computational, memory, and security advantages of previous proofs of quantumness, bringing the community a step closer to establishing the minimal requirements for proofs of quantumness. Additionally, we design a single-round blind remote state preparation protocol (RSP) utilizing the same techniques as our proof of quantumness protocol. A blind RSP protocol is one in which a client delegates the preparation of a quantum state to a remote server without revealing the description of the state. Our protocol is the first single-round blind RSP protocol that allows the client to delegate any single qubit state on a fixed plane of the Bloch sphere, up to a phase flip. Finally, we sketch applications of our techniques to randomness generation, quantum money, and encrypted quantum simulation.

► BibTeX data

@article{Alnawakhtha2024latticebasedquantum,
  doi = {10.22331/q-2024-07-04-1399},
  url = {https://doi.org/10.22331/q-2024-07-04-1399},
  title = {Lattice-{B}ased {Q}uantum {A}dvantage from {R}otated {M}easurements},
  author = {Alnawakhtha, Yusuf and Mantri, Atul and Miller, Carl A. and Wang, Daochen},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1399},
  month = jul,
  year = {2024}
}

► References

[1] Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. One-shot signatures and applications to hybrid quantum/classical authentication. In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC), pages 255–268, 2020. iacr:2020/107. doi:10.1145/3357713.3384304.
https://doi.org/10.1145/3357713.3384304
https://eprint.iacr.org/2020/107

[2] Joël Alwen and Chris Peikert. Generating shorter bases for hard random lattices. Theory of Computing Systems, 48(3):535–553, 2011. iacr:2008/521. doi:10.1007/s00224-010-9278-3.
https://doi.org/10.1007/s00224-010-9278-3
https://eprint.iacr.org/2008/521

[3] Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. Theoretical Computer Science, 560:7–11, 2014. arXiv:2003.06557. doi:10.1016/j.tcs.2014.05.025.
https://doi.org/10.1016/j.tcs.2014.05.025
arXiv:2003.06557

[4] Christian Badertscher, Alexandru Cojocaru, Léo Colisson, Elham Kashefi, Dominik Leichtle, Atul Mantri, and Petros Wallden. Security limitations of classical-client delegated quantum computing. In International Conference on the Theory and Application of Cryptology and Information Security, pages 667–696, 2020. arXiv:2007.01668. doi:10.1007/978-3-030-64834-3_23.
https://doi.org/10.1007/978-3-030-64834-3_23
arXiv:2007.01668

[5] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. J. ACM, 68(5), August 2021. arXiv:1804.00640. doi:10.1145/3441309.
https://doi.org/10.1145/3441309
arXiv:1804.00640

[6] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal blind quantum computation. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), pages 517–526, 2009. arXiv:0807.4154. doi:10.1109/FOCS.2009.36.
https://doi.org/10.1109/FOCS.2009.36
arXiv:0807.4154

[7] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick. Simpler Proofs of Quantumness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), pages 8:1–8:14, 2020. arXiv:2005.04826. doi:10.4230/LIPIcs.TQC.2020.8.
https://doi.org/10.4230/LIPIcs.TQC.2020.8
arXiv:2005.04826

[8] Zvika Brakerski. Quantum FHE (almost) as secure as classical. In Annual International Cryptology Conference, pages 67–95, 2018. iacr:2018/338. doi:10.1007/978-3-319-96878-0_3.
https://doi.org/10.1007/978-3-319-96878-0_3
https://eprint.iacr.org/2018/338

[9] Michele Ciampi, Alexandru Cojocaru, Elham Kashefi, and Atul Mantri. Secure Two-Party Quantum Computation Over Classical Channels, 2020. doi:10.48550/arXiv.2010.07925.
https://doi.org/10.48550/arXiv.2010.07925

[10] Alexandru Cojocaru, Léo Colisson, Elham Kashefi, and Petros Wallden. QFactory: classically-instructed remote secret qubits preparation. In International Conference on the Theory and Application of Cryptology and Information Security, pages 615–645, 2019. arXiv:1904.06303. doi:10.1007/978-3-030-34578-5_22.
https://doi.org/10.1007/978-3-030-34578-5_22
arXiv:1904.06303

[11] Alexandru Cojocaru, Léo Colisson, Elham Kashefi, and Petros Wallden. On the possibility of classical client blind quantum computing. Cryptography, 5(1):3, 2021. arXiv:1802.08759. doi:10.3390/cryptography5010003.
https://doi.org/10.3390/cryptography5010003
arXiv:1802.08759

[12] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23(15):880, 1969. doi:10.1103/PhysRevLett.23.880.
https://doi.org/10.1103/PhysRevLett.23.880

[13] Clément L Canonne, Gautam Kamath, and Thomas Steinke. The Discrete Gaussian for Differential Privacy. In Advances in Neural Information Processing Systems, volume 33, pages 15676–15688, 2020. doi:10.48550/arXiv.2004.00010.
https://doi.org/10.48550/arXiv.2004.00010

[14] Vedran Dunjko, Elham Kashefi, and Anthony Leverrier. Blind quantum computing with weak coherent pulses. Physical Review Letters, 108(20):200502, 2012. arXiv:1108.5571. doi:10.1103/PhysRevLett.108.200502.
https://doi.org/10.1103/PhysRevLett.108.200502
arXiv:1108.5571

[15] S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe. Demonstration of a small programmable quantum computer with atomic qubits. Nature, 536(7614):63–66, 2016. arXiv:1603.04512. doi:10.1038/nature18648.
https://doi.org/10.1038/nature18648
arXiv:1603.04512

[16] Kent A. G. Fisher, Anne Broadbent, L. K. Shalm, Z. Yan, Jonathan Lavoie, Robert Prevedel, Thomas Jennewein, and Kevin J. Resch. Quantum computing on encrypted data. Nature Communications, 5(1):1–7, 2014. arXiv:1309.2586. doi:10.1038/ncomms4074.
https://doi.org/10.1038/ncomms4074
arXiv:1309.2586

[17] Honghao Fu, Daochen Wang, and Qi Zhao. Parallel Self-Testing of EPR Pairs Under Computational Assumptions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP), volume 261, pages 64:1–64:19, 2023. arXiv:2201.13430. doi:10.4230/LIPIcs.ICALP.2023.64.
https://doi.org/10.4230/LIPIcs.ICALP.2023.64
arXiv:2201.13430

[18] Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. Going Beyond Bell's Theorem, pages 69–72. Springer Netherlands, 1989. arXiv:0712.0921. doi:10.1007/978-94-017-0849-4_10.
https://doi.org/10.1007/978-94-017-0849-4_10
arXiv:0712.0921

[19] Alexandru Gheorghiu, Tony Metger, and Alexander Poremba. Quantum Cryptography with Classical Communication: Parallel Remote State Preparation for Copy-Protection, Verification, and More. In 50th International Colloquium on Automata, Languages, and Programming (ICALP), volume 261, pages 67:1–67:17, 2023. arXiv:2201.13445. doi:10.4230/LIPIcs.ICALP.2023.67.
https://doi.org/10.4230/LIPIcs.ICALP.2023.67
arXiv:2201.13445

[20] S. Goldwasser, S. Micali, and R. L. Rivest. A ``Paradoxical'' Solution To The Signature Problem. In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science (FOCS), pages 441–448, 1984. doi:10.1109/SFCS.1984.715946.
https://doi.org/10.1109/SFCS.1984.715946

[21] Alexandru Gheorghiu and Thomas Vidick. Computationally-secure and composable remote state preparation. In Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1024–1033, 2019. arXiv:1904.06320. doi:10.1109/FOCS.2019.00066.
https://doi.org/10.1109/FOCS.2019.00066
arXiv:1904.06320

[22] Shuichi Hirahara and François Le Gall. Test of quantumness with small-depth quantum circuits. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), 2021. arXiv:2105.05500. doi:10.4230/LIPIcs.MFCS.2021.59.
https://doi.org/10.4230/LIPIcs.MFCS.2021.59
arXiv:2105.05500

[23] Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets. Chernoff-Type Direct Product Theorems. Journal of Cryptology, 22(1):75–92, 2009. doi:10.1007/s00145-008-9029-7.
https://doi.org/10.1007/s00145-008-9029-7

[24] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum Advantage from Any Non-local Game. In Proceedings of the 55th ACM Symposium on Theory of Computing (STOC), page 1617–1628, 2023. arXiv:2203.15877v1. doi:10.1145/3564246.3585164.
https://doi.org/10.1145/3564246.3585164
arXiv:2203.15877v1

[25] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, and Norman Y. Yao. Classically verifiable quantum advantage from a computational Bell test. Nature Physics, 18(8):918–924, 2022. arXiv:2104.00687. doi:10.1038/s41567-022-01643-7.
https://doi.org/10.1038/s41567-022-01643-7
arXiv:2104.00687

[26] Zhenning Liu and Alexandru Gheorghiu. Depth-efficient proofs of quantumness. Quantum, 6:807, 2022. arXiv:2107.02163. doi:10.22331/q-2022-09-19-807.
https://doi.org/10.22331/q-2022-09-19-807
arXiv:2107.02163

[27] Urmila Mahadev. Classical Homomorphic Encryption for Quantum Circuits. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS), pages 332–338, 2018. arXiv:1708.02130. doi:10.1109/FOCS.2018.00039.
https://doi.org/10.1109/FOCS.2018.00039
arXiv:1708.02130

[28] Dmitri Maslov. Basic circuit compilation techniques for an ion-trap quantum machine. New Journal of Physics, 19(2):023035, 2017. arXiv:1603.07678. doi:10.1088/1367-2630/aa5e47.
https://doi.org/10.1088/1367-2630/aa5e47
arXiv:1603.07678

[29] Daniele Micciancio and Chris Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In Advances in Cryptology – EUROCRYPT 2012, pages 700–718, 2012. iacr:2011/501. doi:10.1007/978-3-642-29011-4_41.
https://doi.org/10.1007/978-3-642-29011-4_41
https://eprint.iacr.org/2011/501

[30] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa, and Seiichiro Tani. Computational self-testing for entangled magic states. Physical Review A, 106:L010601, 2022. arXiv:2111.02700. doi:10.1103/PhysRevA.106.L010601.
https://doi.org/10.1103/PhysRevA.106.L010601
arXiv:2111.02700

[31] Tony Metger and Thomas Vidick. Self-testing of a single quantum device under computational assumptions. Quantum, 5:544, 2021. arXiv:2001.09161. doi:10.22331/q-2021-09-16-544.
https://doi.org/10.22331/q-2021-09-16-544
arXiv:2001.09161

[32] Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. Efficient Certifiable Randomness from a Single Quantum Device, 2022. doi:10.48550/arXiv.2204.11353.
https://doi.org/10.48550/arXiv.2204.11353

[33] Tomoyuki Morimae and Takashi Yamakawa. Proofs of Quantumness from Trapdoor Permutations. In 14th Innovations in Theoretical Computer Science Conference (ITCS), volume 251, pages 87:1–87:14, 2023. arXiv:2208.12390. doi:10.4230/LIPIcs.ITCS.2023.87.
https://doi.org/10.4230/LIPIcs.ITCS.2023.87
arXiv:2208.12390

[34] National Academies of Sciences, Engineering, and Medicine. Quantum Computing: Progress and Prospects. The National Academies Press, 2019. doi:10.17226/25196.
https://doi.org/10.17226/25196

[35] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. doi:10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[36] Chris Peikert. An Efficient and Parallel Gaussian Sampler for Lattices. In Advances in Cryptology – CRYPTO 2010, pages 80–97, 2010. iacr:2010/088. doi:10.1007/978-3-642-14623-7_5.
https://doi.org/10.1007/978-3-642-14623-7_5
https://eprint.iacr.org/2010/088

[37] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009. doi:10.1145/1568318.1568324.
https://doi.org/10.1145/1568318.1568324

[38] Roy Radian and Or Sattath. Semi-quantum Money. Journal of Cryptology, 35(2), 2022. arXiv:1908.08889. doi:10.1007/s00145-021-09418-8.
https://doi.org/10.1007/s00145-021-09418-8
arXiv:1908.08889

[39] Peter W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science (FOCS), pages 124–134, 1994. arXiv:quant-ph/9508027. doi:10.1109/SFCS.1994.365700.
https://doi.org/10.1109/SFCS.1994.365700
arXiv:quant-ph/9508027

[40] Stephen Wiesner. Conjugate Coding. SIGACT News, 15(1):78–88, 1983. doi:10.1145/1008908.1008920.
https://doi.org/10.1145/1008908.1008920

[41] A. Winter. Coding theorem and strong converse for quantum channels. IEEE Transactions on Information Theory, 45(7):2481–2485, 1999. doi:10.1109/18.796385.
https://doi.org/10.1109/18.796385

[42] Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 69–74, 2022. arXiv:2204.02063. doi:10.1109/FOCS54457.2022.00014.
https://doi.org/10.1109/FOCS54457.2022.00014
arXiv:2204.02063

[43] Jiayu Zhang. Classical verification of quantum computations in linear time. In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 46–57, 2022. arXiv:2202.13997. doi:10.1109/FOCS54457.2022.00012.
https://doi.org/10.1109/FOCS54457.2022.00012
arXiv:2202.13997

[44] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina, and Christopher Monroe. Interactive cryptographic proofs of quantumness using mid-circuit measurements. Nature Physics, 19(11):1725–1731, 2023. arXiv:2112.05156. doi:10.1038/s41567-023-02162-9.
https://doi.org/10.1038/s41567-023-02162-9
arXiv:2112.05156

Cited by

[1] Atul Singh Arora, Kishor Bharti, Alexandru Cojocaru, and Andrea Coladangelo, 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 1106 (2024) ISBN:979-8-3315-1674-1.

[2] Duong Phan, Weiqiang Wen, Xingyu Yan, and Jinwei Zheng, "Zero-Knowledge Proofs of Quantumness", Abstract_only IACR Communications in Cryptology 1 4, cc1-4-46 (2025).

[3] Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, and Katherine Van Kirk, Proceedings of the 57th Annual ACM Symposium on Theory of Computing 1496 (2025) ISBN:9798400715105.

[4] Atul Singh Arora, Kishor Bharti, Alexandru Cojocaru, and Andrea Coladangelo, "A computational test of quantum contextuality, and even simpler proofs of quantumness", arXiv:2405.06787, (2024).

[5] Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton, and Tony Metger, "Single-Round Proofs of Quantumness from Knowledge Assumptions", arXiv:2405.15736, (2024).

[6] Ashutosh Bhatia, Sainath Bitragunta, and Kamlesh Tiwari, "Enhanced Lightweight Quantum Key Distribution Protocol for Improved Efficiency and Security", IEEE Open Journal of the Communications Society 6, 926 (2025).

[7] Gregory D. Kahanamoku-Meyer, "Forging quantum data: classically defeating an IQP-based quantum test", Quantum 7, 1107 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-16 22:25:58) and SAO/NASA ADS (last updated successfully 2026-07-16 22:25:59). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.