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

Quantum Information and Computation

On quantum one-way permutations

Elham Kashefi, H. Nishimura, Vlatko Vedral

Published Aug 1, 2002• 8 citations
Publisher

Abstract

\We discuss the question of the existence of quantum one-way permutations. First, we consider the question: if a state is difficult to prepare, is the reflection operator about that state difficult to construct? By revisiting Grover's algorithm, we present the relationship between this question and the existence of quantum one-way permutations. Next, we prove the equivalence between inverting a permutation and that of constructing polynomial size quantum networks for reflection operators about a class of quantum states. We will consider both the worst case and the average case complexity scenarios for this problem. Moreover, we compare our method to Grover's algorithm and discuss possible applications of our results.

DOI
10.26421/qic2.5-5

Related papers

A note on quantum one-way permutations

Elham Kashefi, Harumichi Nishimura, Vlatko Vedral

We discuss the question of the existence of quantum one-way permutations. First, we prove the equivalence between inverting a permutation and that of constructing a polynomial size network for reflecting about a given quantum state. Next, we consider the question: if a state is difficult to prepare, is the operator reflecting about that state difficult to construct? By revisiting Grover's algorithm, we present the relationship between this question and the existence of one-way permutations. Moreover, we compare our method to Grover's algorithm and discuss possible applications of our results.

arXiv:quant-ph/0109157•Sep 28, 2001•1 citation

On Basing One-way Permutations on NP-hard Problems under Quantum Reductions

Nai-Hui Chia, Sean Hallgren, Fang Song

A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then coNP ⊆ QIP( 2 ) .

arXiv:1804.10309•Quantum•Aug 27, 2020•3 citations

Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States

Jinyoung Ha, Jun Heo

In this paper, we propose a construction method of Grover's algorithm to solve the N-Queen problem. Quantum permutation state was designed and applied to the initialization and amplitude amplification process in Grover's algorithm. An oracle-level quantum circuit was constructed using Boolean algebraic expressions. We reduced the number of iterations of the Grover's algorithm by decreasing the number of superposed inputs in the initialize step using quantum permutation state. We show that our algorithm has less time complexity compared to previous study that solved the N -Queen problem using Grover's algorithm with W state as a input.

International Conference on Information and Communication Technology Convergence (ICTC)•Oct 19, 2022•1 citation

Quantum Search with In-Place Queries

Blake Holman, Ronak Ramachandran, Justin Yirka

Quantum query complexity is typically characterized in terms of XOR queries |x,y> to |x,y+f(x)> or phase queries, which ensure that even queries to non-invertible functions are unitary. When querying a permutation, another natural model is unitary: in-place queries |x> to |f(x)>. Some problems are known to require exponentially fewer in-place queries than XOR queries, but no separation has been shown in the opposite direction. A candidate for such a separation was the problem of inverting a permutation over N elements. This task, equivalent to unstructured search in the context of permutations, is solvable with $O(\sqrt{N})$ XOR queries but was conjectured to require $Ω(N)$ in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using $O(\sqrt{N})$ in-place queries. Our algorithm achieves the same speedup as Grover's algorithm despite the inability to efficiently uncompute queries or perform straightforward oracle-controlled reflections. Nonetheless, we show that there are indeed problems which require fewer XOR queries than in-place queries. We introduce a subspace-conversion problem called Function Erasure that requires 1 XOR query and $Θ(\sqrt{N})$ in-place queries. Then, we build on a recent extension of the quantum adversary method to characterize exact conditions for a decision problem to exhibit such a separation, and we propose a candidate problem.

arXiv:2504.03620•Leibniz international proceedings in informatics•Jan 1, 2025•3 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooks•Apr 26, 2011•1 citation

Hardness of Quantum Distribution Learning and Quantum Cryptography

Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae

The existence of one-way functions (OWFs) forms the minimal assumption in classical cryptography. However, this is not necessarily the case in quantum cryptography. One-way puzzles (OWPuzzs), introduced by Khurana and Tomer, provide a natural quantum analogue of OWFs. The existence of OWPuzzs implies $PP\neq BQP$, while the converse remains open. In classical cryptography, the analogous problem-whether OWFs can be constructed from $P \neq NP$-has long been studied from the viewpoint of hardness of learning. Hardness of learning in various frameworks (including PAC learning) has been connected to OWFs or to $P \neq NP$. In contrast, no such characterization previously existed for OWPuzzs. In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning. Specifically, we prove that OWPuzzs exist if and only if proper quantum distribution learning is hard on average. A natural question that follows is whether the worst-case hardness of proper quantum distribution learning can be derived from $PP \neq BQP$. If so, and a worst-case to average-case hardness reduction is achieved, it would imply OWPuzzs solely from $PP \neq BQP$. However, we show that this would be extremely difficult: if worst-case hardness is PP-hard (in a black-box reduction), then $SampBQP \neq SampBPP$ follows from the infiniteness of the polynomial hierarchy. Despite that, we show that $PP \neq BQP$ is equivalent to another standard notion of hardness of learning: agnostic. We prove that $PP \neq BQP$ if and only if agnostic quantum distribution learning with respect to KL divergence is hard. As a byproduct, we show that hardness of agnostic quantum distribution learning with respect to statistical distance against $PPT^{Σ_3^P}$ learners implies $SampBQP \neq SampBPP$.

arXiv:2507.01292•Jul 2, 2025•5 citations
\We discuss the question of the existence of quantum one-way permutations. First, we consider the question: if a state is difficult to prepare, is the reflection operator about that state difficult to construct? By revisiting Grover's algorithm, we present the relationship between this question and the existence of quantum one-way permutations. Next, we prove the equivalence between inverting a permutation and that of constructing polynomial size quantum networks for reflection operators about a class of quantum states. We will consider both the worst case and the average case complexity scenarios for this problem. Moreover, we compare our method to Grover's algorithm and discuss possible applications of our results.
We discuss the question of the existence of quantum one-way permutations. First, we prove the equivalence between inverting a permutation and that of constructing a polynomial size network for reflecting about a given quantum state. Next, we consider the question: if a state is difficult to prepare, is the operator reflecting about that state difficult to construct? By revisiting Grover's algorithm, we present the relationship between this question and the existence of one-way permutations. Moreover, we compare our method to Grover's algorithm and discuss possible applications of our results.
A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then coNP ⊆ QIP( 2 ) .
In this paper, we propose a construction method of Grover's algorithm to solve the N-Queen problem. Quantum permutation state was designed and applied to the initialization and amplitude amplification process in Grover's algorithm. An oracle-level quantum circuit was constructed using Boolean algebraic expressions. We reduced the number of iterations of the Grover's algorithm by decreasing the number of superposed inputs in the initialize step using quantum permutation state. We show that our algorithm has less time complexity compared to previous study that solved the N -Queen problem using Grover's algorithm with W state as a input.
Quantum query complexity is typically characterized in terms of XOR queries |x,y> to |x,y+f(x)> or phase queries, which ensure that even queries to non-invertible functions are unitary. When querying a permutation, another natural model is unitary: in-place queries |x> to |f(x)>. Some problems are known to require exponentially fewer in-place queries than XOR queries, but no separation has been shown in the opposite direction. A candidate for such a separation was the problem of inverting a permutation over N elements. This task, equivalent to unstructured search in the context of permutations, is solvable with O(N)O(\sqrt{N})O(N​) XOR queries but was conjectured to require Ω(N)Ω(N)Ω(N) in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using O(N)O(\sqrt{N})O(N​) in-place queries. Our algorithm achieves the same speedup as Grover's algorithm despite the inability to efficiently uncompute queries or perform straightforward oracle-controlled reflections. Nonetheless, we show that there are indeed problems which require fewer XOR queries than in-place queries. We introduce a subspace-conversion problem called Function Erasure that requires 1 XOR query and Θ(N)Θ(\sqrt{N})Θ(N​) in-place queries. Then, we build on a recent extension of the quantum adversary method to characterize exact conditions for a decision problem to exhibit such a separation, and we propose a candidate problem.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
The existence of one-way functions (OWFs) forms the minimal assumption in classical cryptography. However, this is not necessarily the case in quantum cryptography. One-way puzzles (OWPuzzs), introduced by Khurana and Tomer, provide a natural quantum analogue of OWFs. The existence of OWPuzzs implies PP≠BQPPP\neq BQPPP=BQP, while the converse remains open. In classical cryptography, the analogous problem-whether OWFs can be constructed from P≠NPP \neq NPP=NP-has long been studied from the viewpoint of hardness of learning. Hardness of learning in various frameworks (including PAC learning) has been connected to OWFs or to P≠NPP \neq NPP=NP. In contrast, no such characterization previously existed for OWPuzzs. In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning. Specifically, we prove that OWPuzzs exist if and only if proper quantum distribution learning is hard on average. A natural question that follows is whether the worst-case hardness of proper quantum distribution learning can be derived from PP≠BQPPP \neq BQPPP=BQP. If so, and a worst-case to average-case hardness reduction is achieved, it would imply OWPuzzs solely from PP≠BQPPP \neq BQPPP=BQP. However, we show that this would be extremely difficult: if worst-case hardness is PP-hard (in a black-box reduction), then SampBQP≠SampBPPSampBQP \neq SampBPPSampBQP=SampBPP follows from the infiniteness of the polynomial hierarchy. Despite that, we show that PP≠BQPPP \neq BQPPP=BQP is equivalent to another standard notion of hardness of learning: agnostic. We prove that PP≠BQPPP \neq BQPPP=BQP if and only if agnostic quantum distribution learning with respect to KL divergence is hard. As a byproduct, we show that hardness of agnostic quantum distribution learning with respect to statistical distance against PPTΣ3PPPT^{Σ_3^P}PPTΣ3P​ learners implies SampBQP≠SampBPPSampBQP \neq SampBPPSampBQP=SampBPP.