Algorithms · Quantum query algorithm
Matrix products over semirings
Compute the product of two n × n matrices over a semiring rather than a ring — the (max, min) product, the distance product, and the Boolean product — where the absence of subtraction rules out the fast algebraic algorithms that make ring matrix multiplication cost n^ω. The question the paper poses is whether anything beats the Õ(n^(5/2)) that follows from applying Grover search or quantum minimum-finding entry by entry.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupStated by the primary source: "In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity O(n^2.687)."
- Reported costO(n^2.473) for the (max, min) product of two n × n matrices, against O(n^2.687) for the best known classical algorithm. For the distance product, the ℓ most significant bits of each entry are computed in O(2^(0.64ℓ) n^2.46). The sparse Boolean product is given as a four-case piecewise bound in the number of non-zero entries, and the paper says its algorithm performs better when n^1.151 < m < n^(ω−1/2).
- Papers1
Compute the product of two n × n matrices over a semiring rather than a ring — the (max, min) product, the distance product, and the Boolean product — where the absence of subtraction rules out the fast algebraic algorithms that make ring matrix multiplication cost n^ω. The question the paper poses is whether anything beats the Õ(n^(5/2)) that follows from applying Grover search or quantum minimum-finding entry by entry. Le Gall and Nishimura introduce what they call quantum enumeration, a variant of Grover's search, and apply it to a problem they define as the generalized existence dominance product, which generalizes the existence dominance product of Duan and Pettie. The classical Duan-Pettie approach combines a search step with classical algebraic rectangular matrix multiplication; the paper adapts that combination to the quantum setting, then reduces the (max, min) product, the most significant bits of the distance product, and the sparse Boolean product to instances of the generalized product. The result is the first pair of quantum algorithms that beat the straightforward entrywise Õ(n^(5/2)) and, for these semirings, the best classical algorithms as well, without assuming anything about sparsity.
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 →
Le Gall and Nishimura introduce what they call quantum enumeration, a variant of Grover's search, and apply it to a problem they define as the generalized existence dominance product, which generalizes the existence dominance product of Duan and Pettie. The classical Duan-Pettie approach combines a search step with classical algebraic rectangular matrix multiplication; the paper adapts that combination to the quantum setting, then reduces the (max, min) product, the most significant bits of the distance product, and the sparse Boolean product to instances of the generalized product. The result is the first pair of quantum algorithms that beat the straightforward entrywise Õ(n^(5/2)) and, for these semirings, the best classical algorithms as well, without assuming anything about sparsity. 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. Stated by the primary source: "In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity O(n^2.687).". Reported cost: O(n^2.473) for the (max, min) product of two n × n matrices, against O(n^2.687) for the best known classical algorithm. For the distance product, the ℓ most significant bits of each entry are computed in O(2^(0.64ℓ) n^2.46). The sparse Boolean product is given as a four-case piecewise bound in the number of non-zero entries, and the paper says its algorithm performs better when n^1.151 < m < n^(ω−1/2)..
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
- Stated by the primary source: "In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity O(n^2.687)."
- Reported cost
- O(n^2.473) for the (max, min) product of two n × n matrices, against O(n^2.687) for the best known classical algorithm. For the distance product, the ℓ most significant bits of each entry are computed in O(2^(0.64ℓ) n^2.46). The sparse Boolean product is given as a four-case piecewise bound in the number of non-zero entries, and the paper says its algorithm performs better when n^1.151 < m < n^(ω−1/2).
- Speedup class
- Polynomial (checked against the record's own primary paper, which states it)
- Complexity basis
- abstract of arXiv:1310.3898: "We construct a quantum algorithm computing the product of two n × n matrices over the (max, min) semiring with time complexity O(n^2.473)." and "We construct a quantum algorithm computing the ℓ most significant bits of each entry of the distance product of two n × n matrices in time O(2^0.64ℓ n^2.46)."; the classical figure is the abstract's own: "In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity O(n^2.687)."; section 1 for the sparse regime: "Our algorithm performs better when n^1.151 < m < n^(ω−1/2)".
- 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 products over semirings
PROBLEM: Compute the product of two n × n matrices over a semiring rather than a ring — the (max, min) product, the distance product, and the Boolean product — where the absence of subtraction rules out the fast algebraic algorithms that make ring matrix multiplication cost n^ω. The question the paper poses is whether anything beats the Õ(n^(5/2)) that follows from applying Grover search or quantum minimum-finding entry by entry.
IDEA: Le Gall and Nishimura introduce what they call quantum enumeration, a variant of Grover's search, and apply it to a problem they define as the generalized existence dominance product, which generalizes the existence dominance product of Duan and Pettie. The classical Duan-Pettie approach combines a search step with classical algebraic rectangular matrix multiplication; the paper adapts that combination to the quantum setting, then reduces the (max, min) product, the most significant bits of the distance product, and the sparse Boolean product to instances of the generalized product. The result is the first pair of quantum algorithms that beat the straightforward entrywise Õ(n^(5/2)) and, for these semirings, the best classical algorithms as well, without assuming anything about sparsity.
REPORTED COST: O(n^2.473) for the (max, min) product of two n × n matrices, against O(n^2.687) for the best known classical algorithm. For the distance product, the ℓ most significant bits of each entry are computed in O(2^(0.64ℓ) n^2.46). The sparse Boolean product is given as a four-case piecewise bound in the number of non-zero entries, and the paper says its algorithm performs better when n^1.151 < m < n^(ω−1/2).
BASIS: abstract of arXiv:1310.3898: "We construct a quantum algorithm computing the product of two n × n matrices over the (max, min) semiring with time complexity O(n^2.473)." and "We construct a quantum algorithm computing the ℓ most significant bits of each entry of the distance product of two n × n matrices in time O(2^0.64ℓ n^2.46)."; the classical figure is the abstract's own: "In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity O(n^2.687)."; section 1 for the sparse regime: "Our algorithm performs better when n^1.151 < m < n^(ω−1/2)".
PRIMARY SOURCE: François Le Gall, Harumichi Nishimura (2013), Quantum Algorithms for Matrix Products over Semirings — https://arxiv.org/abs/1310.3898
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
- Subset finding by quantum walk
Algorithms
- Element distinctness by quantum walk
Algorithms
- Grover unstructured search
Algorithms
References
- Quantum Algorithms for Matrix Products over Semirings
François Le Gall, Harumichi Nishimura · 2013
Primary source, and the source of both the quantum and the classical figures this record compares. Consult it for the unit-cost oracle model of section 2 that every stated complexity depends on, for the generalized existence dominance product the reductions all pass through, and for the regime conditions attached to the distance-product and sparse Boolean results.