On quantum one-way permutations

Elham Kashefi, Harumichi Nishimura, Vlatko Vedral

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Pages (from-to)379-398
Number of pages20
JournalQuantum Information and Computation
Volume2
Issue number5
Publication statusPublished - 2002

Fingerprint Dive into the research topics of 'On quantum one-way permutations'. Together they form a unique fingerprint.

Cite this