Algorithms · Quantum query algorithm
Matrix rank by a span program
Given oracle access to the integer entries of an n×m matrix A, determine the rank of A.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costO(√(r(n-r+1)) L T) queries to the entries of an n×m integer matrix A under a promise that the rank of A is at least r, where L is the root-mean-square of the reciprocals of the r largest singular values of A and T is a factor set by the sparsity of A: T = O(√(nm)) for general A, and T = O(k log(n+m)) when A has at most k nonzero entries in any row or column. The Zoo gives the classical cost as order nm queries. Every figure here is the Zoo's; the paper's own abstract states no query count.
- Papers2
Given oracle access to the integer entries of an n×m matrix A, determine the rank of A. Belovs' paper opens from the statement that span programs have recently been shown to be equivalent to quantum query algorithms, calls it an open problem whether that equivalence can be used to come up with new quantum algorithms, and addresses that problem by providing span programs for some linear algebra problems. It develops a notion of a high level span program, which abstracts away the loading of input vectors into a span program, and gives such a high level span program for the rank problem. Its closing section reduces a high level span program to an ordinary span program, which known quantum query algorithms can then evaluate. The Zoo describes the result as an algorithm that can use fewer queries than the classical order-nm cost given a promise that the rank of the matrix is at least r, with the count depending on the r largest singular values of A and on how sparse A is.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Belovs' paper opens from the statement that span programs have recently been shown to be equivalent to quantum query algorithms, calls it an open problem whether that equivalence can be used to come up with new quantum algorithms, and addresses that problem by providing span programs for some linear algebra problems. It develops a notion of a high level span program, which abstracts away the loading of input vectors into a span program, and gives such a high level span program for the rank problem. Its closing section reduces a high level span program to an ordinary span program, which known quantum query algorithms can then evaluate. The Zoo describes the result as an algorithm that can use fewer queries than the classical order-nm cost given a promise that the rank of the matrix is at least r, with the count depending on the r largest singular values of A and on how sparse A is. This record's speedup class, "Polynomial", is a secondary source's classification of the oracular algorithms it files this under — not a claim its primary paper makes. Not checked against the primary source yet. Reported cost: O(√(r(n-r+1)) L T) queries to the entries of an n×m integer matrix A under a promise that the rank of A is at least r, where L is the root-mean-square of the reciprocals of the r largest singular values of A and T is a factor set by the sparsity of A: T = O(√(nm)) for general A, and T = O(k log(n+m)) when A has at most k nonzero entries in any row or column. The Zoo gives the classical cost as order nm queries. Every figure here is the Zoo's; the paper's own abstract states no query count..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial
- Primary source on the speedup
- Not checked against the primary source yet
- Reported cost
- O(√(r(n-r+1)) L T) queries to the entries of an n×m integer matrix A under a promise that the rank of A is at least r, where L is the root-mean-square of the reciprocals of the r largest singular values of A and T is a factor set by the sparsity of A: T = O(√(nm)) for general A, and T = O(k log(n+m)) when A has at most k nonzero entries in any row or column. The Zoo gives the classical cost as order nm queries. Every figure here is the Zoo's; the paper's own abstract states no query count.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity basis
- Quantum Algorithm Zoo entry "Matrix Rank" (LaTeX rendered into Unicode): "Belovs' algorithm uses O(√(r(n-r+1))LT) queries, where L is the root-mean-square of the reciprocals of the r largest singular values of A and T is a factor that depends on the sparsity of the matrix. For general A , T = O(√(nm)) . If A has at most k nonzero entries in any row or column then T = O(k log(n+m))"; the classical side and the problem statement are from the same entry: "Suppose we are given oracle access to the (integer) entries of an n × m matrix A . We wish to determine the rank of the matrix. Classically this requires order nm queries." The abstract of arXiv:1103.0842 quotes no query count, gate count or runtime anywhere; it describes the construction only, closing "The last section of the paper deals with reducing a high level span program to an ordinary span program that can be solved using known quantum query algorithms." The bound above therefore rests on the Zoo entry alone, not on the primary paper's abstract.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Quantum query algorithm with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Matrix rank by a span program
PROBLEM: Given oracle access to the integer entries of an n×m matrix A, determine the rank of A.
IDEA: Belovs' paper opens from the statement that span programs have recently been shown to be equivalent to quantum query algorithms, calls it an open problem whether that equivalence can be used to come up with new quantum algorithms, and addresses that problem by providing span programs for some linear algebra problems. It develops a notion of a high level span program, which abstracts away the loading of input vectors into a span program, and gives such a high level span program for the rank problem. Its closing section reduces a high level span program to an ordinary span program, which known quantum query algorithms can then evaluate. The Zoo describes the result as an algorithm that can use fewer queries than the classical order-nm cost given a promise that the rank of the matrix is at least r, with the count depending on the r largest singular values of A and on how sparse A is.
REPORTED COST: O(√(r(n-r+1)) L T) queries to the entries of an n×m integer matrix A under a promise that the rank of A is at least r, where L is the root-mean-square of the reciprocals of the r largest singular values of A and T is a factor set by the sparsity of A: T = O(√(nm)) for general A, and T = O(k log(n+m)) when A has at most k nonzero entries in any row or column. The Zoo gives the classical cost as order nm queries. Every figure here is the Zoo's; the paper's own abstract states no query count.
BASIS: Quantum Algorithm Zoo entry "Matrix Rank" (LaTeX rendered into Unicode): "Belovs' algorithm uses O(√(r(n-r+1))LT) queries, where L is the root-mean-square of the reciprocals of the r largest singular values of A and T is a factor that depends on the sparsity of the matrix. For general A , T = O(√(nm)) . If A has at most k nonzero entries in any row or column then T = O(k log(n+m))"; the classical side and the problem statement are from the same entry: "Suppose we are given oracle access to the (integer) entries of an n × m matrix A . We wish to determine the rank of the matrix. Classically this requires order nm queries." The abstract of arXiv:1103.0842 quotes no query count, gate count or runtime anywhere; it describes the construction only, closing "The last section of the paper deals with reducing a high level span program to an ordinary span program that can be solved using known quantum query algorithms." The bound above therefore rests on the Zoo entry alone, not on the primary paper's abstract.
PRIMARY SOURCE: Aleksandrs Belovs (2011), Span-program-based quantum algorithm for the rank problem — https://arxiv.org/abs/1103.0842
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
References
- Span-program-based quantum algorithm for the rank problem
Aleksandrs Belovs · 2011
Primary source. It provides span programs for some linear algebra problems, develops the notion of a high level span program that abstracts from loading input vectors into a span program, gives a high level span program for the rank problem, and reduces it to an ordinary span program solvable by known quantum query algorithms. The abstract states no query count, so the cost claim recorded here comes from the Zoo entry rather than from this paper; consult the paper itself for the analysis behind it.
- Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
Ben W. Reichardt · 2009
Companion source for the equivalence the primary paper opens from. Belovs' abstract states that span programs have recently been shown to be equivalent to quantum query algorithms without naming a source for it, and this paper states that equivalence as a result of its own. It turns the general adversary bound, a semi-definite program that lower-bounds quantum query complexity, into an upper bound: one SDP outputs for any boolean function a span program of optimal witness size, that optimal witness size is shown to coincide with the general adversary bound, and a quantum algorithm evaluates span programs with only a logarithmic query overhead on the witness size. The paper states the resulting universality in both directions, that a good quantum query algorithm for a problem implies a good span program and vice versa, and it reports a corollary of an optimal quantum algorithm for evaluating balanced formulas over any finite boolean gate set.