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

IEEE/ACIS International Conference on Computer and Information Science (ICIS)

Comparison between New Quantum Approaches for Finding the Minimum or the Maximum of an Unsorted Set of Integers

Mir Shahriar Emami, Mohammad Reza Fattahi, Hossein Keshmiri

Published May 1, 2008• 3 citations
Publisher

Abstract

The change has already begun. It is not a simple change but a revolution in the sense of speed and its impact. In this paper we are going to discuss on quantum computer as a physical system and discuss on its main weakness and then based on our new approach we have solved a problem for finding the minimum or the maximum of a set of integers which has not been solved based on previous quantum computing approach with time complexity about O(1) and then we evaluate and comprise it with another quantum algorithm with time complexity about 0(1+radic(n)) which also is given by us and as a result we show that if the size of quantum resister is low then our first quantum approach which has lower time complexity is satisfactory and if the size of quantum register is high then as the probability of success of our first approach decreases so our second approach is more convenient.

DOI
10.1109/icis.2008.74

Related papers

Quantum min / max algorithms based on qubits {00, 11}

Ammar Odeh, Eman Abdelfattah

Quantum algorithms have gained a lot of consideration especially for the need to find out the extreme values like minimum or maximum. This paper introduces novel quantum algorithms to figure out the minimum and the maximum numbers among a set of positive integer numbers by employing some of the quantum features such as superposition, entanglement, and probability. The proposed algorithms utilize qubits properties to accelerate the searching process.

IEEE Long Island Systems, Applications and Technology Conference (LISAT)•May 1, 2017•0 citations

Optimization on a Novel Quantum Greedy Approach Based on Learning Strategy for Zero and One Knapsack Problem and Evaluation

Mir Shahriar Emami

Now a days probabilistic approach can be a convenient solution for solving many of the problems especially the problems with high time complexity like as knapsack problem. In this paper I present a new quantum computation approach based on learning strategy and greedy approach for solving the zero and one knapsack problem with polynomial time complexity about O (n) and as a result of evaluation of my presented approach I show that the probability of success of the given approach is low based on disentangled quantum registers and without learning the past observations. Nevertheless I show that how learning approach can significantly increases the probability of success of the given quantum greedy method. Also as an another result of evaluation of the presented approach I show that if the standard deviation of the items increases, the probability of success of the given new learning approach increases too.

International Conference on Machine Learning and Applications•Jan 1, 2008•1 citation

Quantum algorithms for finding extrema with unary predicates

Man Hon Chan

We study the problem of finding the maximum or the minimum of a given set S = {x₀, X₁, ... X n₋₁}, each element X i drawn from some finite universe [Unary] of real numbers. We assume that the inputs are abstracted within an oracle O where we can only gain information through unary comparisons in the form "Is Xi greater than, equal to, or less than some constant k?" Classically, this problem is solved optimally with a runtime of Θ(n +lg|U|). In the setting of Quantum Computing, we show that at least Ω(√n+lg|U|) queries are required to solve the problem even with bounded error. Combining variants of the Grover's search [1, 2] algorithm and the optimal classical unary extrema finding algorithm, we have derived a series of new quantum algorithms, some running in time as fast as O(√n lg*n+lg|U|). This shows that quantum computers can accelerate the speed in the unary comparison model asymptotically. Inspecting our tools, we find convincing arguments that our lower bound is most probably tight, but we may need an entirely new approach to solve the problem optimally. The technique used in our algorithm can also be extended to solve variations of quantum statistics problems. For instance, our result can be directly extended to approximation of extrema of real numbers, similar to that of [3]. Moreover, we can also solve the quantum k-select problem optimally in time O(√kn) with constant success probability. We hope that our ideas and tools will prove to be useful in other areas.

•Jan 1, 2011•0 citations

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

A Comparison of Security and its Performance for Key Agreements in Post-Quantum Cryptography

Fábio Borges, Paulo Ricardo Reis, Diogo Augusto Barros Pereira

Nowadays, we are surrounded by devices collecting and transmitting private information. Currently, the two main mathematical problems that guarantee security on the Internet are the Integer Factorization Problem and the Discrete Logarithm Problem. However, Shor's quantum algorithm can easily solve both problems. Therefore, research into cryptographic algorithms that run in classical computers and are resistant to quantum computers is extremely necessary. This area is known as post-quantum cryptography and usually studies asymmetric cryptography. By means of asymptotic analysis, the purpose of this paper is to provide an evaluation of security and its performance for the types of cryptographic systems considered safe against quantum attacks in the second-round NIST Post-Quantum Standardization Process, namely isogeny cryptosystems based on supersingular elliptic curves, error correction code-based encryption system, and lattice-based ring learning with errors. We performed a security comparison of Key Agreements protocols based on these three post-quantum cryptographic primitives and compared them with Discrete Logarithm Problem and Integer Factorization Problem. The comparison of security and its performance is presented by security level, the former by complexity analyses to achieve theoretical minimum key sizes, and the latter by simulation to assess a practical performance comparison. In the complexity analysis, as we increase the security level and then the size of the cryptographic keys increases, techniques based on isogeny outperform all other post-quantum algorithms in relation to key sizes at practical security level. In the performance comparison, the results show that the code-based protocol presents the best results among the others.

IEEE Access•Jan 1, 2020•69 citations

A NEW QUANTUM ALGORITHM FOR SOLVING THE MINIMUM SEARCHING PROBLEM

Luis Antônio Brasil Kowada, Carlile Lavor, Renato Portugal +1 more

In this paper, we propose a new quantum algorithm for solving the minimum searching problem. This algorithm has the same order of time and space complexities as the algorithm proposed by Dürr and Høyer, but it provides a quadratic reduction in the number of measurements. In addition to the correctness and complexity analysis of the algorithm, we present simulation results considering an NP-hard problem.

International Journal of Quantum Information•Jun 1, 2008•11 citations
The change has already begun. It is not a simple change but a revolution in the sense of speed and its impact. In this paper we are going to discuss on quantum computer as a physical system and discuss on its main weakness and then based on our new approach we have solved a problem for finding the minimum or the maximum of a set of integers which has not been solved based on previous quantum computing approach with time complexity about O(1) and then we evaluate and comprise it with another quantum algorithm with time complexity about 0(1+radic(n)) which also is given by us and as a result we show that if the size of quantum resister is low then our first quantum approach which has lower time complexity is satisfactory and if the size of quantum register is high then as the probability of success of our first approach decreases so our second approach is more convenient.
Now a days probabilistic approach can be a convenient solution for solving many of the problems especially the problems with high time complexity like as knapsack problem. In this paper I present a new quantum computation approach based on learning strategy and greedy approach for solving the zero and one knapsack problem with polynomial time complexity about O (n) and as a result of evaluation of my presented approach I show that the probability of success of the given approach is low based on disentangled quantum registers and without learning the past observations. Nevertheless I show that how learning approach can significantly increases the probability of success of the given quantum greedy method. Also as an another result of evaluation of the presented approach I show that if the standard deviation of the items increases, the probability of success of the given new learning approach increases too.
We study the problem of finding the maximum or the minimum of a given set S = {x₀, X₁, ... X n₋₁}, each element X i drawn from some finite universe [Unary] of real numbers. We assume that the inputs are abstracted within an oracle O where we can only gain information through unary comparisons in the form "Is Xi greater than, equal to, or less than some constant k?" Classically, this problem is solved optimally with a runtime of Θ(n +lg|U|). In the setting of Quantum Computing, we show that at least Ω(√n+lg|U|) queries are required to solve the problem even with bounded error. Combining variants of the Grover's search [1, 2] algorithm and the optimal classical unary extrema finding algorithm, we have derived a series of new quantum algorithms, some running in time as fast as O(√n lg*n+lg|U|). This shows that quantum computers can accelerate the speed in the unary comparison model asymptotically. Inspecting our tools, we find convincing arguments that our lower bound is most probably tight, but we may need an entirely new approach to solve the problem optimally. The technique used in our algorithm can also be extended to solve variations of quantum statistics problems. For instance, our result can be directly extended to approximation of extrema of real numbers, similar to that of [3]. Moreover, we can also solve the quantum k-select problem optimally in time O(√kn) with constant success probability. We hope that our ideas and tools will prove to be useful in other areas.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Nowadays, we are surrounded by devices collecting and transmitting private information. Currently, the two main mathematical problems that guarantee security on the Internet are the Integer Factorization Problem and the Discrete Logarithm Problem. However, Shor's quantum algorithm can easily solve both problems. Therefore, research into cryptographic algorithms that run in classical computers and are resistant to quantum computers is extremely necessary. This area is known as post-quantum cryptography and usually studies asymmetric cryptography. By means of asymptotic analysis, the purpose of this paper is to provide an evaluation of security and its performance for the types of cryptographic systems considered safe against quantum attacks in the second-round NIST Post-Quantum Standardization Process, namely isogeny cryptosystems based on supersingular elliptic curves, error correction code-based encryption system, and lattice-based ring learning with errors. We performed a security comparison of Key Agreements protocols based on these three post-quantum cryptographic primitives and compared them with Discrete Logarithm Problem and Integer Factorization Problem. The comparison of security and its performance is presented by security level, the former by complexity analyses to achieve theoretical minimum key sizes, and the latter by simulation to assess a practical performance comparison. In the complexity analysis, as we increase the security level and then the size of the cryptographic keys increases, techniques based on isogeny outperform all other post-quantum algorithms in relation to key sizes at practical security level. In the performance comparison, the results show that the code-based protocol presents the best results among the others.