Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2302.04749 · Lecture notes in computer science

Quantum Advantage from One-Way Functions

Tomoyuki Morimae, Takashi Yamakawa

Published Jan 1, 2024• 9 citations
arXivHTMLPDF
DOI
10.1007/978-3-031-68388-6_13

Related papers

Quantum One-Way Function

Tao Shang

Springer eBooks•Oct 15, 2024•0 citations

Universal construction of a full quantum one-way function

Yao Tang, Tao Shang, Jianwei Liu

Quantum Information Processing•Jul 26, 2022•4 citations

Quantum Pessiland

Boyang Chen, Tomoyuki Morimae, Takashi Yamakawa

Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of $UP\cap coUP$ implies $P^{\#P}\not\subseteq i.o.BQP/qpoly$, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from $P^{\#P}\not\subseteq i.o.BQP/qpoly$, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].

quant-pharXiv:2608.29493•Sep 1, 2026•0 citations

Cryptographic Characterization of Quantum Advantage

Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa

Quantum computational advantage refers to an existence of computational tasks that are easy for quantum computing but hard for classical one. Unconditionally showing quantum advantage is beyond our current understanding of complexity theory, and therefore some computational assumptions are needed. Which complexity assumption is necessary and sufficient for quantum advantage? In this paper, we show that inefficient-verifier proofs of quantumness (IV-PoQ) exist if and only if classically-secure one-way puzzles (OWPuzzs) exist. As far as we know, this is the first time that a complete cryptographic characterization of quantum advantage is obtained. IV-PoQ capture various types of quantum advantage previously studied, such as sampling-based quantum advantage and searching-based one. Previous work [Morimae and Yamakawa, Crypto 2024] showed that IV-PoQ can be constructed from OWFs, but a construction of IV-PoQ from weaker assumptions was left open. Our result solves the open problem. OWPuzzs are one of the most fundamental quantum cryptographic primitives implied by many quantum cryptographic primitives weaker than one-way functions (OWFs). The equivalence between IV-PoQ and classically-secure OWPuzzs therefore highlights that if there is no quantum advantage, then these fundamental primitives do not exist. The equivalence also means that quantum advantage is an example of the applications of OWPuzzs. Except for commitments, no application of OWPuzzs was known before. Our result shows that quantum advantage is another application of OWPuzzs, which solves the open question of [Chung, Goldin, and Gray, Crypto 2024]. Moreover, it is the first quantum-computation-classical-communication (QCCC) application of OWPuzzs.

arXiv:2410.00499•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•8 citations

One-Way Quantumness

Anonymous

Physics•Apr 21, 2016•0 citations

Experimental Boson Sampling Enabling Cryptographic One-Way Function

Xiao‐Wei Wang, Wen-Hao Zhou, Yu-Xuan Fu +9 more

Boson sampling is a computational problem, which is commonly believed to be a representative paradigm for attaining the milestone of quantum advantage. So far, massive efforts have been made to the experimental large-scale boson sampling for demonstrating this milestone, while further applications of the machines remain a largely unexplored area. Here, we investigate experimentally the efficiency and security of a cryptographic one-way function that relies on coarse-grained boson sampling, in the framework of a photonic boson-sampling machine fabricated by a femtosecond laser direct writing technique. Our findings demonstrate that the implementation of the function requires moderate sample sizes, which can be over 4 orders of magnitude smaller than the ones predicted by the Chernoff bound; whereas for numbers of photons n≥3 and bins d∼poly(m,n), the same output of the function cannot be generated by nonboson samplers. Our Letter is the first experimental study that deals with the potential applications of boson sampling in the field of cryptography and paves the way toward additional studies in this direction.

Physical Review Letters•Feb 9, 2023•6 citations
Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which UP∩coUPUP\cap coUPUP∩coUP is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which UP∩coUPUP\cap coUPUP∩coUP is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of UP∩coUPUP\cap coUPUP∩coUP implies P#P⊈i.o.BQP/qpolyP^{\#P}\not\subseteq i.o.BQP/qpolyP#P⊆i.o.BQP/qpoly, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from P#P⊈i.o.BQP/qpolyP^{\#P}\not\subseteq i.o.BQP/qpolyP#P⊆i.o.BQP/qpoly, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].
Quantum computational advantage refers to an existence of computational tasks that are easy for quantum computing but hard for classical one. Unconditionally showing quantum advantage is beyond our current understanding of complexity theory, and therefore some computational assumptions are needed. Which complexity assumption is necessary and sufficient for quantum advantage? In this paper, we show that inefficient-verifier proofs of quantumness (IV-PoQ) exist if and only if classically-secure one-way puzzles (OWPuzzs) exist. As far as we know, this is the first time that a complete cryptographic characterization of quantum advantage is obtained. IV-PoQ capture various types of quantum advantage previously studied, such as sampling-based quantum advantage and searching-based one. Previous work [Morimae and Yamakawa, Crypto 2024] showed that IV-PoQ can be constructed from OWFs, but a construction of IV-PoQ from weaker assumptions was left open. Our result solves the open problem. OWPuzzs are one of the most fundamental quantum cryptographic primitives implied by many quantum cryptographic primitives weaker than one-way functions (OWFs). The equivalence between IV-PoQ and classically-secure OWPuzzs therefore highlights that if there is no quantum advantage, then these fundamental primitives do not exist. The equivalence also means that quantum advantage is an example of the applications of OWPuzzs. Except for commitments, no application of OWPuzzs was known before. Our result shows that quantum advantage is another application of OWPuzzs, which solves the open question of [Chung, Goldin, and Gray, Crypto 2024]. Moreover, it is the first quantum-computation-classical-communication (QCCC) application of OWPuzzs.
Boson sampling is a computational problem, which is commonly believed to be a representative paradigm for attaining the milestone of quantum advantage. So far, massive efforts have been made to the experimental large-scale boson sampling for demonstrating this milestone, while further applications of the machines remain a largely unexplored area. Here, we investigate experimentally the efficiency and security of a cryptographic one-way function that relies on coarse-grained boson sampling, in the framework of a photonic boson-sampling machine fabricated by a femtosecond laser direct writing technique. Our findings demonstrate that the implementation of the function requires moderate sample sizes, which can be over 4 orders of magnitude smaller than the ones predicted by the Chernoff bound; whereas for numbers of photons n≥3 and bins d∼poly(m,n), the same output of the function cannot be generated by nonboson samplers. Our Letter is the first experimental study that deals with the potential applications of boson sampling in the field of cryptography and paves the way toward additional studies in this direction.