2001/09/28 by Elham Kashefi, Kashefi, Elham, Harumichi Nishimura +3
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0109157
9 pages
arxiv created 2001/09/28 · openalex publication_date 2001/09/28 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.