Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0507060 · Quantum Information Processing

On the Complexity of Searching for a Maximum of a Function on a Quantum Computer

Maciej Goćwin

Published Feb 1, 2006• 6 citations
arXivHTMLPDF
DOI
10.1007/s11128-006-0011-8

Related papers

Quantum Algorithms and Complexity for Continuous Problems

Anargyros Papageorgiou, Joseph F. Traub

Springer eBooks•Nov 2, 2011•0 citations

Complexity of Searching Maximum of a Function on Quantum Computer

Maciej Goćwin

In this paper we deal with a problem of finding maximum of a function from the Holder class on quantum computer. We present matching lower and upper bounds on the complexity of this problem in the quantum query model. We prove upper bounds by constructing an algorithm that uses the algorithm for finding maximum of discrete sequence. To prove lower bounds we use result for finding logical OR of sequence of bits. We show that quantum computer yields a quadratic speed-up over deterministic and randomized algorithms.

•Jul 6, 2005•1 citation

On the Basic Algorithms of Quantum Computation

昌史 木村

•Mar 14, 2001•0 citations

Quantum Speedup for Polar Maximum Likelihood Decoding

Shintaro Fujiwara, Naoki Ishikawa

Conventional decoding algorithms for polar codes strive to balance achievable performance and computational complexity in classical computing. While maximum likelihood (ML) decoding guarantees optimal performance, its NP-hard nature makes it impractical for real-world systems. In this letter, we propose a novel ML decoding architecture for polar codes based on the Grover adaptive search, a quantum exhaustive search algorithm. Unlike conventional studies, our approach, enabled by a newly formulated objective function, uniquely supports Gray-coded multi-level modulation without expanding the search space size compared to the classical ML decoding. Simulation results demonstrate that our proposed quantum decoding achieves ML performance while providing a pure quadratic speedup in query complexity.

arXiv:2411.04727•Nov 7, 2024•2 citations

Recent Developments in Quantum Algorithms and Complexity

Andris Ambainis

Lecture notes in computer science•Jan 1, 2014•1 citation

Quantum Existence Testing and Its Application for Finding Extreme Values in Unsorted Databases

Sándor Imre

Many information processing and computing problems can be traced back to find the extreme value of a database or a function. Unfortunately, classical solutions suffer from high computational complexity if the database is unsorted or, equivalently, the function has many local minimum/maximum points. Proposed quantum computing-based solutions involve the repeated application of Grower's searching algorithm. In this paper, we introduce a new technique exploiting the parallel processing capabilities of quantum computing in a different way. We derive a special case of quantum counting - we call it quantum existence testing - which allows adapting the classical logarithmic search algorithm so that it is suitable for structured databases to unstructured ones. The paper analyzes the required number of database queries, the corresponding computational complexity, and the probability of error and their relationship

IEEE Transactions on Computers•Apr 17, 2007•31 citations
In this paper we deal with a problem of finding maximum of a function from the Holder class on quantum computer. We present matching lower and upper bounds on the complexity of this problem in the quantum query model. We prove upper bounds by constructing an algorithm that uses the algorithm for finding maximum of discrete sequence. To prove lower bounds we use result for finding logical OR of sequence of bits. We show that quantum computer yields a quadratic speed-up over deterministic and randomized algorithms.
Conventional decoding algorithms for polar codes strive to balance achievable performance and computational complexity in classical computing. While maximum likelihood (ML) decoding guarantees optimal performance, its NP-hard nature makes it impractical for real-world systems. In this letter, we propose a novel ML decoding architecture for polar codes based on the Grover adaptive search, a quantum exhaustive search algorithm. Unlike conventional studies, our approach, enabled by a newly formulated objective function, uniquely supports Gray-coded multi-level modulation without expanding the search space size compared to the classical ML decoding. Simulation results demonstrate that our proposed quantum decoding achieves ML performance while providing a pure quadratic speedup in query complexity.
Many information processing and computing problems can be traced back to find the extreme value of a database or a function. Unfortunately, classical solutions suffer from high computational complexity if the database is unsorted or, equivalently, the function has many local minimum/maximum points. Proposed quantum computing-based solutions involve the repeated application of Grower's searching algorithm. In this paper, we introduce a new technique exploiting the parallel processing capabilities of quantum computing in a different way. We derive a special case of quantum counting - we call it quantum existence testing - which allows adapting the classical logarithmic search algorithm so that it is suitable for structured databases to unstructured ones. The paper analyzes the required number of database queries, the corresponding computational complexity, and the probability of error and their relationship