Quantum queries on permutations

DOI10.1007/978-3-319-19225-3_15MaRDI QIDQ5500691zbMATH OpenOpenAlexFDO

Authors Taisia Mischenko-Slatenkova, Alina Vasilieva, Ilja Kucevalovs, Rūsiņš Freivalds

Publication date 7 August 2015

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-19225-3_15

Mathematics Subject Classification ID

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

Recommendations

• Quantum Queries on Permutations with a Promise
• On the number of queries necessary to identify a permutation
• Inverting a permutation is as hard as unordered search
• The query complexity of order-finding
• Quantum complexity of permutations

Cites work

• Algebraic factoring and geometry theorem proving
• Complexity measures and decision tree complexity: a survey.
• scientific article; zbMATH DE number 4030991 (Why is no real title available?)
• scientific article; zbMATH DE number 1500513 (Why is no real title available?)
• Implementation and Application of Automata
• Quantum algorithms revisited
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum Queries on Permutations with a Promise
• Rapid solution of problems by quantum computation

Cited in

(11)

• Revisiting Deutsch-Jozsa algorithm
• 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
• The query complexity of finding a hidden permutation
• Quantum Circuits for the Unitary Permutation Problem
• Inverting a permutation is as hard as unordered search
• Quantum Queries on Permutations with a Promise
• On the number of queries necessary to identify a permutation
• scientific article; zbMATH DE number 1756014 (Why is no real title available?)
• A note on the quantum query complexity of permutation symmetric functions
• Single-query learning from abelian and non-abelian Hamming distance oracles

This page was built for publication: Quantum queries on permutations

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