Conference on Innovations in Theoretical Computer Science

Adversary lower bound for the k-sum problem

Aleksandrs Belovs, Robert Špalek

Published Jan 3, 2013• 38 citations

Abstract

We prove a tight quantum query lower bound Omega(nk/(k+1)) for the problem of deciding whether there exist k numbers among n that sum up to a prescribed number, provided that the alphabet size is sufficiently large.

DOI: 10.1145/2422436.2422474

Related papers

Adversary Lower Bound for the k-sum Problem

Aleksandrs Belovs, Robert Špalek

arXiv:1206.6528Jun 27, 20127 citations

Adversary Lower Bound for the Orthogonal Array Problem

Robert Špalek

arXiv:1304.0845Apr 3, 20134 citations

Adversary lower bounds for the collision and the set equality problems

BelovsAleksandrs, RosmanisAnsis

We prove tight Ω(n1/3) lower bounds on the quantum query complexity of the Collision and the SET EQUALITY problems, provided that the size of the alphabet is large enough. We do this using the nega...

Quantum Information and ComputationMar 1, 20180 citations

Elementary proofs of quantum lower bounds for element distinctness and k-sum

Andris Ambainis, Martins Kokainis

quant-pharXiv:2610.32693Oct 26, 20260 citations

Adversary lower bounds for the collision and the set equality problems

Aleksandrs Belovs, Ansis Rosmanis

We prove tight \Omega(n^{1/3}) lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough. We do this using the negative-weight adversary method. Thus, we reprove the result by Aaronson and Shi, as well as a more recent development by Zhandry.

arXiv:1310.5185Quantum Information and ComputationMar 1, 201813 citations

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

Alexander Valtchev

May 27, 20150 citations

Conference on Innovations in Theoretical Computer Science

Adversary lower bound for the k-sum problem

Aleksandrs Belovs, Robert Špalek

Published Jan 3, 2013• 38 citations

Publisher

Abstract

DOI: 10.1145/2422436.2422474

Related papers

Adversary Lower Bound for the k-sum Problem

Aleksandrs Belovs, Robert Špalek

We prove a tight quantum query lower bound $Ω(n^{k/(k+1)})$ for the problem of deciding whether there exist $k$ numbers among $n$ that sum up to a prescribed number, provided that the alphabet size is sufficiently large. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.We prove a tight quantum query lower bound $Ω(n^{k/(k+1)})$ for the problem of deciding whether there exist $k$ numbers among $n$ that sum up to a prescribed number, provided that the alphabet size is sufficiently large. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.

arXiv:1206.6528Jun 27, 20127 citations

Adversary Lower Bound for the Orthogonal Array Problem

Robert Špalek

We prove a quantum query lower bound Ω(n^{(d+1)/(d+2)}) for the problem of deciding whether an input string of size n contains a k-tuple which belongs to a fixed orthogonal array on k factors of strength d<=k-1 and index 1, provided that the alphabet size is sufficiently large. Our lower bound is tight when d=k-1. The orthogonal array problem includes the following problems as special cases: k-sum problem with d=k-1, k-distinctness problem with d=1, k-pattern problem with d=0, (d-1)-degree problem with 1<=d<=k-1, unordered search with d=0 and k=1, and graph collision with d=0 and k=2.We prove a quantum query lower bound Ω(n^{(d+1)/(d+2)}) for the problem of deciding whether an input string of size n contains a k-tuple which belongs to a fixed orthogonal array on k factors of strength d<=k-1 and index 1, provided that the alphabet size is sufficiently large. Our lower bound is tight when d=k-1. The orthogonal array problem includes the following problems as special cases: k-sum problem with d=k-1, k-distinctness problem with d=1, k-pattern problem with d=0, (d-1)-degree problem with 1<=d<=k-1, unordered search with d=0 and k=1, and graph collision with d=0 and k=2.

arXiv:1304.0845Apr 3, 20134 citations

Adversary lower bounds for the collision and the set equality problems

BelovsAleksandrs, RosmanisAnsis

Quantum Information and ComputationMar 1, 20180 citations

Elementary proofs of quantum lower bounds for element distinctness and k-sum

Andris Ambainis, Martins Kokainis

We give elementary proofs of the $Ω(n^{2/3})$ quantum query lower bound for element distinctness and the $Ω(n^{k/(k+1)})$ lower bound for the $k$ -sum problem, for fixed $k$ and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.We give elementary proofs of the $Ω(n^{2/3})$ quantum query lower bound for element distinctness and the $Ω(n^{k/(k+1)})$ lower bound for the $k$-sum problem, for fixed $k$ and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.

quant-pharXiv:2610.32693Oct 26, 20260 citations

Adversary lower bounds for the collision and the set equality problems

Aleksandrs Belovs, Ansis Rosmanis

arXiv:1310.5185Quantum Information and ComputationMar 1, 201813 citations

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.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, 20150 citations

We prove a tight quantum query lower bound

Ω(n^{k/(k+1)})

for the problem of deciding whether there exist

k

numbers among

n

that sum up to a prescribed number, provided that the alphabet size is sufficiently large. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.

We give elementary proofs of the

Ω(n^{2/3})

quantum query lower bound for element distinctness and the

Ω(n^{k/(k+1)})

lower bound for the

k

-sum problem, for fixed

k

and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.

\\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.