The query complexity of order-finding

DOI10.1016/J.IC.2004.04.001zbMATH Open1069.68054arXivquant-ph/9911124OpenAlexW1973682419MaRDI QIDQ596296FDOQ596296

Richard Cleve

Publication date: 10 August 2004

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithms revisited
• On the Power of Quantum Computation
• Quantum Complexity Theory
• The Difference Between Consecutive Primes
• Zeros of L-functions
• Primes in short intervals

Cited In (10)

• Deterministic algorithms for the hidden subgroup problem
• Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
• On the optimal order of worst case complexity of direct search
• Sample complexity of hidden subgroup problem
• Query order in the polynomial hierarchy
• Title not available (Why is that?)
• Query Order
• Symmetries, graph properties, and quantum speedups
• Property testing for cyclic groups and beyond
• Quantum algorithms for algebraic problems

Recommendations

• Title not available (Why is that?) 👍 👎
• On the optimal order of worst case complexity of direct search 👍 👎
• The complexity of querying indefinite data about linearly ordered domains 👍 👎
• On the Complexity of Some Ordering Problems 👍 👎
• On the complexity of searching in trees and partially ordered structures 👍 👎
• The complexity of higher-order queries 👍 👎
• On algorithms to find \(p\)-ordering 👍 👎

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)