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

International Conference for Advancement in Technology (ICONAT)

Computational Time Complexity for Sorting Algorithm amalgamated with Quantum Search

Anurag Dutta, John Harshith, Yash Soni, Avdhesh Gupta, Vishan Kumar Gupta, Ankit Gupta

Published Jan 24, 2023• 17 citations
Publisher

Abstract

In the pursuit of knowledge, data is a distinct set of values that convey information, describing quantity, quality, facts, statistics, or simple units of meaning, better known as datum. Now, handling data, in the latest world is really a tedious job that includes all the principles related to data management as a valuable resource. Amidst all data management techniques, Sorting is the most important one. Sorting refers to arranging data in ascending or descending order according to linear relationships between data items. It involves mathematical rigour that causes data units to be arranged in a monotonic order by it’s magnitude. In modern world of informatics, Quantum Computing have caught great heights. So, have the algorithms fused to it. Quantum computing is a type of computation whose operation can exploit quantum mechanical phenomena, such as superposition, interference, and entanglement. In this work, we would try to define a lower bound for the Computational Complexity of Sorting Algorithm, being heterogeneity by the lower bound for Quantum Search of an ordered list. Further, we would also develop a upper bound on the Sorting integrated using Grover’s Search- a real time unstructured Quantum Search.

DOI
10.1109/iconat57137.2023.10080217

Related papers

Evolution of Quantum Computing Based on Grover's Search Algorithm

Prakhar Shrivastava, Kapil Kumar Soni, Akhtar Rasool

Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 1, 2019•18 citations

Quantum Search using Grover’s Algorithm: Principles, Performance, and Applications

Anggit Gusti Nugraheni, Heri Mahyuzar, Sri Hastuti

Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.

Asian journal of mathematics and computer research•Jun 23, 2026•0 citations

COMPARATIVE ANALYSIS OF QUANTUM AND CLASSICAL ALGORITHMS IN MODERN COMPUTING

Y.U. Serdaliyev, А.С. Баймаханова

This article is an overview and comparative analysis of quantum and classical algorithms in the field of computing. In the modern world, there is a period of development of high technologies. In this age, it is very effective to realize the goals that humanity has set for itself, not only using the human brain, but also using the thinking properties of the machine. The areas of artificial intelligence and machine learning are developing very rapidly, which allows you to solve tasks that were previously considered exclusively human prerogative. For the classical approach, a quick sort is used to preorder the list, and then the target element is searched. The quantum approach uses Grover's algorithm, which takes advantage of quantum computing to quickly find an item in an unordered list. The comparison results include the execution time of each algorithm and the elements found. This work demonstrates the potential of quantum algorithms in solving search problems and provides a practical example of comparing classical and quantum methods. Machine learning is the main way to optimize and automate processes in production and other industries. quantum computing performed on quantum computers and its own state «quantum machine learning» is the technology of the future. However, despite all the advantages, these technologies are currently poorly studied. Based on a literature review, the formulation of hypotheses, the use of programming methods and the conduct of experiments, the study provides new insights into the application of different types of algorithms to different problems. The results highlight the unique advantages of quantum algorithms in highly specialized problems, the limitations in their use due to technological calls, and suggest a hybrid approach as the future of computing.

Q A Iasaýı atyndaǵy Halyqaralyq qazaq-túrіk ýnıversıtetіnіń habarlary (fızıka matematıka ınformatıka serııasy)•Mar 30, 2024•0 citations

Quantum Computing Algorithms for Solving Complex Mathematical Problems

Et al. Lalit Mohan Trivedi

The power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.

International Journal on Recent and Innovation Trends in Computing and Communication•Nov 7, 2023•1 citation

Quantum time-space tradeoffs for sorting

Hartmut Klauck

We investigate the complexity of sorting in the model of sequential quantum circuits. While it is known that in general a quantum algorithm based on comparisons alone cannot outperform classical sorting algorithms by more than a constant factor in time complexity, this is wrong in a space bounded setting. We observe that for all storage bounds n/log ≥ S ≥ log3n, one can devise a quantum algorithm that sorts n numbers (using comparisons only) in time T=O(n3/2 log3/2 n/√S). We then show the following lower bound on the time-space tradeoff for sorting n numbers from a polynomial size range in a general sorting algorithm (not necessarily based on comparisons): TS=Ω(n3/2). Hence for small values of S the upper bound is almost tight. Classically the time-space tradeoff for sorting is TS=Θ(n2).

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•28 citations

Computational Time Complexity for k-Sum Problem Amalgamated with Quantum Search

Anurag Dutta, John Harshith, K. Lakshmanan +1 more

The k - Sum Problem, which is a generic member of the family of which 2 - Sum and 3 - Sum problems are the youngest siblings is one of the most interesting problems in the domain of Optimization Techniques. Many researchers have shown that the k - Sum problem can be solved in no less than the order of $n_{k-1}$. On the other side, many researchers have tried and have successfully minimized its Computational Complexity, though quite negligibly. But since any subtle method doesn’t exist to minimize its Computational Complexity by a major pie, the Query - “Can k - Sum problem be solved in $O(n_{k-1-\epsilon})$ for some $\epsilon \gt 0$ ” have been added in the list of UPCS (Unsolved Problems in Computer Science). In this article, we will effort to analyse the Complexity of Computing the $k - Sum$ problem, by exemplifying minimal bounds of Quantum Search, $\Omega\left(\frac{\sqrt[2]{\log _2 n}}{\log _2\left(\log _2 n\right)}\right)$ as stated by Buhrman. Now, one assumption that this minimal bound holds is that the element to be searched will be composed in some ordered manner. To extrude that, we will extend our work by making use of Grover’s Search, with Computational Complexity of the order, $O(\sqrt[2]{n})$, which is not known to make use of any prerequisite.

•Apr 21, 2023•3 citations
In the pursuit of knowledge, data is a distinct set of values that convey information, describing quantity, quality, facts, statistics, or simple units of meaning, better known as datum. Now, handling data, in the latest world is really a tedious job that includes all the principles related to data management as a valuable resource. Amidst all data management techniques, Sorting is the most important one. Sorting refers to arranging data in ascending or descending order according to linear relationships between data items. It involves mathematical rigour that causes data units to be arranged in a monotonic order by it’s magnitude. In modern world of informatics, Quantum Computing have caught great heights. So, have the algorithms fused to it. Quantum computing is a type of computation whose operation can exploit quantum mechanical phenomena, such as superposition, interference, and entanglement. In this work, we would try to define a lower bound for the Computational Complexity of Sorting Algorithm, being heterogeneity by the lower bound for Quantum Search of an ordered list. Further, we would also develop a upper bound on the Sorting integrated using Grover’s Search- a real time unstructured Quantum Search.
Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.
Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.
This article is an overview and comparative analysis of quantum and classical algorithms in the field of computing. In the modern world, there is a period of development of high technologies. In this age, it is very effective to realize the goals that humanity has set for itself, not only using the human brain, but also using the thinking properties of the machine. The areas of artificial intelligence and machine learning are developing very rapidly, which allows you to solve tasks that were previously considered exclusively human prerogative. For the classical approach, a quick sort is used to preorder the list, and then the target element is searched. The quantum approach uses Grover's algorithm, which takes advantage of quantum computing to quickly find an item in an unordered list. The comparison results include the execution time of each algorithm and the elements found. This work demonstrates the potential of quantum algorithms in solving search problems and provides a practical example of comparing classical and quantum methods. Machine learning is the main way to optimize and automate processes in production and other industries. quantum computing performed on quantum computers and its own state «quantum machine learning» is the technology of the future. However, despite all the advantages, these technologies are currently poorly studied. Based on a literature review, the formulation of hypotheses, the use of programming methods and the conduct of experiments, the study provides new insights into the application of different types of algorithms to different problems. The results highlight the unique advantages of quantum algorithms in highly specialized problems, the limitations in their use due to technological calls, and suggest a hybrid approach as the future of computing.
The power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.
We investigate the complexity of sorting in the model of sequential quantum circuits. While it is known that in general a quantum algorithm based on comparisons alone cannot outperform classical sorting algorithms by more than a constant factor in time complexity, this is wrong in a space bounded setting. We observe that for all storage bounds n/log ≥ S ≥ log3n, one can devise a quantum algorithm that sorts n numbers (using comparisons only) in time T=O(n3/2 log3/2 n/√S). We then show the following lower bound on the time-space tradeoff for sorting n numbers from a polynomial size range in a general sorting algorithm (not necessarily based on comparisons): TS=Ω(n3/2). Hence for small values of S the upper bound is almost tight. Classically the time-space tradeoff for sorting is TS=Θ(n2).
The k - Sum Problem, which is a generic member of the family of which 2 - Sum and 3 - Sum problems are the youngest siblings is one of the most interesting problems in the domain of Optimization Techniques. Many researchers have shown that the k - Sum problem can be solved in no less than the order of nk−1n_{k-1}nk−1​. On the other side, many researchers have tried and have successfully minimized its Computational Complexity, though quite negligibly. But since any subtle method doesn’t exist to minimize its Computational Complexity by a major pie, the Query - “Can k - Sum problem be solved in O(nk−1−ϵ)O(n_{k-1-\epsilon})O(nk−1−ϵ​) for some ϵ>0\epsilon \gt 0ϵ>0 ” have been added in the list of UPCS (Unsolved Problems in Computer Science). In this article, we will effort to analyse the Complexity of Computing the k−Sumk - Sumk−Sum problem, by exemplifying minimal bounds of Quantum Search, Ω(log⁡2n2log⁡2(log⁡2n))\Omega\left(\frac{\sqrt[2]{\log _2 n}}{\log _2\left(\log _2 n\right)}\right)Ω(log2​(log2​n)2log2​n​​) as stated by Buhrman. Now, one assumption that this minimal bound holds is that the element to be searched will be composed in some ordered manner. To extrude that, we will extend our work by making use of Grover’s Search, with Computational Complexity of the order, O(n2)O(\sqrt[2]{n})O(2n​), which is not known to make use of any prerequisite.