Quantum Queries on Permutations with a Promise

DOI10.1007/978-3-642-02979-0_24MaRDI QIDQ3637358zbMATH OpenOpenAlexFDO

Authors Rūsiņš Freivalds, Kazuo Iwama

Publication date 9 July 2009

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02979-0_24

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Recommendations

• Quantum queries on permutations
• The structure of promises in quantum speedups
• The query complexity of order-finding
• On the number of queries necessary to identify a permutation
• Inverting a permutation is as hard as unordered search

Cites work

• Complexity measures and decision tree complexity: a survey.
• scientific article; zbMATH DE number 1500513 (Why is no real title available?)
• Quantum algorithms revisited
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Rapid solution of problems by quantum computation

Cited in

(13)

• Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives
• Quantum complexity of permutations
• Quantum Circuits for the Unitary Permutation Problem
• Inverting a permutation is as hard as unordered search
• Multi-query quantum sums
• On the number of queries necessary to identify a permutation
• Superiority of exact quantum automata for promise problems
• Determining the parity of a permutation using an experimental NMR qutrit
• A note on the quantum query complexity of permutation symmetric functions
• The structure of promises in quantum speedups
• Single-query learning from abelian and non-abelian Hamming distance oracles
• Quantum queries on permutations
• Ultrametric automata and Turing machines

This page was built for publication: Quantum Queries on Permutations with a Promise

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637358)