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:1306.5039 · Open Systems & Information Dynamics

On Quantum Algorithm for Binary Search and Its Computational Complexity

Satoshi Iriyama, Makoto Ohya, Igor Vasil'evich Volovich

Published Sep 1, 2015• 9 citations
arXivHTMLPDF

Abstract

A new quantum algorithm for the search problem and its computational complexity are discussed. Its essential part is the use of the so-called chaos amplifier, [8, 9, 10, 13]. It is shown that for the search problem containing [Formula: see text] objects time complexity of the method is polynomial in [Formula: see text].
DOI
10.1142/s1230161215500195

Related papers

A COMBINED QUANTUM ALGORITHM AND ITS COMPUTATIONAL COMPLEXITY

Satoshi Iriyama

A quantum algorithm for the general search problem is proposed by Ohya et al . in 2015. An NP-hard problem can be solved in polynomial steps with high probability by the quantum algorithm which implicates multiple quantum computation. Each quantum algorithm amplifies the success probability using the special dynamics, so called the Chaos amplifier, which is defined by the logistic map. In 2017, we showed that the Chaos amplifier and more general amplification process can be represented by the GKSL master equation in a two-qubit system. In this study, we explain our notion of combined quantum algorithm, and discuss on its computational complexity for the difficult problem.

Infinite Dimensional Analysis Quantum Probability and Related Topics•Nov 1, 2023•0 citations

QUANTUM ALGORITHM FOR PROTEIN FOLDING AND ITS COMPUTATIONAL COMPLEXITY

Satoshi Iriyama, Makoto Ohya, Ichiro Yamato

We have studied applications of quantum algorithm for the problems in bioinformatics. The protein folding problem is known as one of the difficult problems which we do not solve in polynomial time of input data. We constructed a quantum algorithm for the protein folding problem using our new quantum binary search algorithm, and discussed its computtational complexity. We prove that the computational complexity is polynomial of the number of molecular in the simulation.

QP-PQ, quantum probability and white noise analysis•Mar 1, 2013•0 citations

On New Quantum Search Algorithms and Complexity of NP-Complete Problems

Dhananjay P. Mehendale

We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!

•Jul 1, 2016•0 citations

Abnormal Quantum State Search Based on Parallel Phase Comparison

Guanlei Xu, Xiaogang Xu, Xiaotong Wang

We discuss the problem of filtering out abnormal states from a larger number of quantum states. For this type of problem with [Formula: see text] items to be searched, both the traditional search by enumeration and classical Grover search algorithm have the complexity about [Formula: see text]. In this letter a novel quantum search scheme with exponential speed up is proposed for abnormal states. First, a new comprehensive quantum operator is well-designed to extract the superposition state containing all abnormal states with unknown number [Formula: see text] with complexity [Formula: see text] in probability 1 via well-designed parallel phase comparison. Then, every abnormal state is achieved respectively from [Formula: see text] abnormal states via [Formula: see text] times’ measurement. Finally, a numerical example is given to show the efficiency of the proposed scheme.

Parallel Processing Letters•Nov 9, 2021•0 citations

A formulation of a matrix sparsity approach for the quantum ordered search algorithm

Jupinder Parmar, Saarim Rahman, Jaskaran Thiara

One specific subset of quantum algorithms is Grovers Ordered Search Problem (OSP), the quantum counterpart of the classical binary search algorithm, which utilizes oracle functions to produce a specified value within an ordered database. Classically, the optimal algorithm is known to have a [Formula: see text] complexity; however, Grovers algorithm has been found to have an optimal complexity between the lower bound of [Formula: see text] and the upper bound of [Formula: see text]. We sought to lower the known upper bound of the OSP. With Farhi et al. MITCTP 2815 (1999), arXiv:quant-ph/9901059], we see that the OSP can be resolved into a translational invariant algorithm to create quantum query algorithm restraints. With these restraints, one can find Laurent polynomials for various [Formula: see text] — queries — and [Formula: see text] — database sizes — thus finding larger recursive sets to solve the OSP and effectively reducing the upper bound. These polynomials are found to be convex functions, allowing one to make use of convex optimization to find an improvement on the known bounds. According to Childs et al. [Phys. Rev. A 75 (2007) 032335], semidefinite programming, a subset of convex optimization, can solve the particular problem represented by the constraints. We were able to implement a program abiding to their formulation of a semidefinite program (SDP), leading us to find that it takes an immense amount of storage and time to compute. To combat this setback, we then formulated an approach to improve results of the SDP using matrix sparsity. Through the development of this approach, along with an implementation of a rudimentary solver, we demonstrate how matrix sparsity reduces the amount of time and storage required to compute the SDP — overall ensuring further improvements will likely be made to reach the theorized lower bound.

arXiv:1610.02117•International Journal of Quantum Information•Jan 13, 2017•1 citation

New quantum algorithm solving the NP complete problem

Makoto Ohya

We review the quantum chaos algorithm solving the NP-complete problems in polynomial time. This work has been done in the series of papers with Professor Igor Volovich for nearly ten years.

P-Adic Numbers Ultrametric Analysis and Applications•Feb 1, 2012•0 citations
A quantum algorithm for the general search problem is proposed by Ohya et al . in 2015. An NP-hard problem can be solved in polynomial steps with high probability by the quantum algorithm which implicates multiple quantum computation. Each quantum algorithm amplifies the success probability using the special dynamics, so called the Chaos amplifier, which is defined by the logistic map. In 2017, we showed that the Chaos amplifier and more general amplification process can be represented by the GKSL master equation in a two-qubit system. In this study, we explain our notion of combined quantum algorithm, and discuss on its computational complexity for the difficult problem.
We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!
We discuss the problem of filtering out abnormal states from a larger number of quantum states. For this type of problem with [Formula: see text] items to be searched, both the traditional search by enumeration and classical Grover search algorithm have the complexity about [Formula: see text]. In this letter a novel quantum search scheme with exponential speed up is proposed for abnormal states. First, a new comprehensive quantum operator is well-designed to extract the superposition state containing all abnormal states with unknown number [Formula: see text] with complexity [Formula: see text] in probability 1 via well-designed parallel phase comparison. Then, every abnormal state is achieved respectively from [Formula: see text] abnormal states via [Formula: see text] times’ measurement. Finally, a numerical example is given to show the efficiency of the proposed scheme.
One specific subset of quantum algorithms is Grovers Ordered Search Problem (OSP), the quantum counterpart of the classical binary search algorithm, which utilizes oracle functions to produce a specified value within an ordered database. Classically, the optimal algorithm is known to have a [Formula: see text] complexity; however, Grovers algorithm has been found to have an optimal complexity between the lower bound of [Formula: see text] and the upper bound of [Formula: see text]. We sought to lower the known upper bound of the OSP. With Farhi et al. MITCTP 2815 (1999), arXiv:quant-ph/9901059], we see that the OSP can be resolved into a translational invariant algorithm to create quantum query algorithm restraints. With these restraints, one can find Laurent polynomials for various [Formula: see text] — queries — and [Formula: see text] — database sizes — thus finding larger recursive sets to solve the OSP and effectively reducing the upper bound. These polynomials are found to be convex functions, allowing one to make use of convex optimization to find an improvement on the known bounds. According to Childs et al. [Phys. Rev. A 75 (2007) 032335], semidefinite programming, a subset of convex optimization, can solve the particular problem represented by the constraints. We were able to implement a program abiding to their formulation of a semidefinite program (SDP), leading us to find that it takes an immense amount of storage and time to compute. To combat this setback, we then formulated an approach to improve results of the SDP using matrix sparsity. Through the development of this approach, along with an implementation of a rudimentary solver, we demonstrate how matrix sparsity reduces the amount of time and storage required to compute the SDP — overall ensuring further improvements will likely be made to reach the theorized lower bound.