The query complexity of order-finding

DOI10.1016/J.IC.2004.04.001MaRDI QIDQ596296zbMATH OpenOpenAlexFDO

Authors Richard Cleve

Publication date 10 August 2004

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/9911124

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68)

Abstract: We consider the problem where P is an unknown permutation on {0,1,...,2^n - 1}, y is an element of {0,1,...,2^n - 1}, and the goal is to determine the minimum r > 0 such that P^r(y) = y (where P^r is P composed with itself r times). Information about P is available only via queries that yield P^x(y) from any x in {0,1,...,2^m - 1} and y in {0,1,...,2^n - 1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.

Recommendations

• The complexity of higher-order queries
• On the Complexity of Some Ordering Problems
• The complexity of querying indefinite data about linearly ordered domains
• scientific article; zbMATH DE number 1543293
• On algorithms to find \(p\)-ordering
• On the complexity of searching in trees and partially ordered structures
• On the optimal order of worst case complexity of direct search

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• On the Power of Quantum Computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Primes in short intervals
• Quantum Complexity Theory
• Quantum algorithms revisited
• The Difference Between Consecutive Primes
• Zeros of L-functions

Cited in

(14)

• Quantum algorithms for algebraic problems
• Deterministic algorithms for the hidden subgroup problem
• On the optimal order of worst case complexity of direct search
• Sample complexity of hidden subgroup problem
• Query order in the polynomial hierarchy
• Forrelation: a problem that optimally separates quantum from classical computing
• scientific article; zbMATH DE number 1091107 (Why is no real title available?)
• Query Order
• Symmetries, graph properties, and quantum speedups
• The query complexity of finding a hidden permutation
• Inverting a permutation is as hard as unordered search
• Quantum complexity of permutations
• Quantum Queries on Permutations with a Promise
• Quantum queries on permutations

This page was built for publication: The query complexity of order-finding

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