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

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

Anurag Dutta, John Harshith, K. Lakshmanan, A. Ramamoorthy

Published Apr 21, 2023• 3 citations
Publisher

Abstract

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.

DOI
10.1109/icaia57370.2023.10169278

Related papers

The Subset Sum Problem: Reducing Time Complexity of NP-Completeness with Quantum Search

Bo Moon

The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.

Undergraduate Journal of Mathematical Modeling One + Two•May 1, 2013•3 citations

Computational Time Complexity for Sorting Algorithm amalgamated with Quantum Search

Anurag Dutta, John Harshith, Yash Soni +3 more

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.

International Conference for Advancement in Technology (ICONAT)•Jan 24, 2023•17 citations

Solving the Subset Sum Problem via Quantum Walk Search

Giacomo Lancellotti, Simone Perriello, Alessandro Barenghi +1 more

Quantum walk-based search algorithms have demonstrated an asymptotic quadratic speedup compared to classical search methods. Formulating a generic search problem as a (quantum) search over a graph makes the efficiency of the algorithm to be closely dependent on the properties of the graph itself. In this work, we present a complete implementation of a quantum walk search procedure on Johnson graphs, speeding up the solution of the Subset Sum Problem, a well-known computational problem with applications in resource allocation, scheduling, and cryptanalysis. We provide a detailed design of each sub-circuit, quantifying their costs in terms of gate count, circuit depth, and qubit width, and exhibit all figures of merit as a function of the problem parameters. Our approach includes two distinct implementations: one that minimizes qubit usage and another focused on optimizing circuit depth. We compare our solutions against the unstructured Grover based quantum search algorithm, demonstrating a reduction of the cost on terms of T-count and T-depth, for practically solvable instances. The proposed design serves as a foundational building block for the development of efficient quantum search algorithms that can be modeled on Johnson graphs, bridging the gap with existing theoretical complexity analyses.

IEEE Transactions on Computers•Oct 27, 2025•1 citation

Optimal Success Bounds for Single Query Quantum Algorithms Computing the General SUM Problem

Alexander Valtchev

In this thesis the problem of computing the sum of a string of arbitrary finite length drawn from an arbitrary finite alphabet is treated. The resource considered is the number of queries to some oracle which hides the string and gives access to each of its digits. The sum of a string is defined as adding all of the string's digits together modulo the alphabet size. \n \nClassically, this problem is straightforward as any less than a number of queries equal to the string length reveals no useful information about the sum of the string. In the quantum information setting however, things are not so clear. When the alphabet size is equal to two, the problem becomes finding the parity of a bit string. This is a seminal result in quantum computation that allows a correct answer with certainty by making only half the queries that are classically needed. As the alphabet size increases beyond two however, less is known. There is an algorithm by Meyer and Pommersheim which computes the sum in this general setting with probability of success: $\\min\\left\\lbrace\\frac{\\floor{\\frac{n}{n-q}}}{k}, 1\\right\\rbrace$ where $n$ is the string length, $k$ is the alphabet size, and $q$ is the number of queries made. This algorithm has probability of success slightly above guessing when the number of queries are half the string length, and perfect probability of success when $n-1$ queries are made. The question dealt with in this thesis is whether this algorithm is optimal for the general sum case. \n \nThe problem is expressed as a semidefinite program, given for all instances. The instance for strings of length two and algorithms making a single query is solved and a proof is given. Significant insight into the multi-query case is also provided.

•May 27, 2015•0 citations

Lower Bounds on Quantum Query Complexity

Peter Høyer, Robert Špalek

Shor's and Grover's famous quantum algorithms for factoring and searching show that quantum computers can solve certain computational problems significantly faster than any classical computer. We discuss here what quantum computers_cannot_ do, and specifically how to prove limits on their computational power. We cover the main known techniques for proving lower bounds, and exemplify and compare the methods.

arXiv:quant-ph/0509153•Sep 21, 2005•51 citations

Quantum Computational Complexity Theory and Lower Bounds

Phillip Kaye, Raymond Laflamme, Michele Mosca

We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.

Oxford University Press eBooks•Nov 16, 2006•0 citations
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.
The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.
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 walk-based search algorithms have demonstrated an asymptotic quadratic speedup compared to classical search methods. Formulating a generic search problem as a (quantum) search over a graph makes the efficiency of the algorithm to be closely dependent on the properties of the graph itself. In this work, we present a complete implementation of a quantum walk search procedure on Johnson graphs, speeding up the solution of the Subset Sum Problem, a well-known computational problem with applications in resource allocation, scheduling, and cryptanalysis. We provide a detailed design of each sub-circuit, quantifying their costs in terms of gate count, circuit depth, and qubit width, and exhibit all figures of merit as a function of the problem parameters. Our approach includes two distinct implementations: one that minimizes qubit usage and another focused on optimizing circuit depth. We compare our solutions against the unstructured Grover based quantum search algorithm, demonstrating a reduction of the cost on terms of T-count and T-depth, for practically solvable instances. The proposed design serves as a foundational building block for the development of efficient quantum search algorithms that can be modeled on Johnson graphs, bridging the gap with existing theoretical complexity analyses.
In this thesis the problem of computing the sum of a string of arbitrary finite length drawn from an arbitrary finite alphabet is treated. The resource considered is the number of queries to some oracle which hides the string and gives access to each of its digits. The sum of a string is defined as adding all of the string's digits together modulo the alphabet size. \n \nClassically, this problem is straightforward as any less than a number of queries equal to the string length reveals no useful information about the sum of the string. In the quantum information setting however, things are not so clear. When the alphabet size is equal to two, the problem becomes finding the parity of a bit string. This is a seminal result in quantum computation that allows a correct answer with certainty by making only half the queries that are classically needed. As the alphabet size increases beyond two however, less is known. There is an algorithm by Meyer and Pommersheim which computes the sum in this general setting with probability of success: minleftlbracefracfloorfracnn−qk,1rightrbrace\\min\\left\\lbrace\\frac{\\floor{\\frac{n}{n-q}}}{k}, 1\\right\\rbraceminleftlbracefracfloorfracnn−qk,1rightrbrace where nnn is the string length, kkk is the alphabet size, and qqq is the number of queries made. This algorithm has probability of success slightly above guessing when the number of queries are half the string length, and perfect probability of success when n−1n-1n−1 queries are made. The question dealt with in this thesis is whether this algorithm is optimal for the general sum case. \n \nThe problem is expressed as a semidefinite program, given for all instances. The instance for strings of length two and algorithms making a single query is solved and a proof is given. Significant insight into the multi-query case is also provided.
We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.