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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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.
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.
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)..
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.
Compare Quantum query algorithm with the strongest classical method for the same instance, input budget, and output metric.
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
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.
arxiv.org/abs/1310.3898 ↗