Algorithms · Quantum query algorithm
Commutativity testing of a matrix set by quantum walk
Given oracle access to k matrices of size n × n, where a query names a matrix index x together with a pair of indices i, j and returns the ij entry of the x-th matrix, decide whether all k of the matrices commute with one another.
Attested & literatureUpdated
A small worked example, computed in your browser. It is not a result from this record's papers.
A discrete-time quantum walk on a 4-cycle
One coin qubit, two position qubits (4 positions on a cycle), 3 steps starting at position 0.
Step 1 of 3 · Quantum walk step (4-cycle)
Probability of each outcome after this step
- 01150%
- 11050%
Flips the coin with a Hadamard, then shifts the position by +1 if the coin is |1⟩ or -1 mod 4 if the coin is |0⟩; with the coin in superposition, both shifts happen at once, entangling coin and position.
Probability leaves the outcome it was on and appears on 2 entirely different ones — not one outcome is populated both before and after. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
The same coin flip and shift, applied again.
Probability leaves all 2 outcomes it was on and appears on 4 entirely different ones — not one outcome is populated both before and after.
The same coin flip and shift, a third time.
Probability leaves all 4 outcomes it was on and appears on 2 entirely different ones — not one outcome is populated both before and after. The entanglement comes apart here: each qubit has a state of its own again.
Readout The position always reads 3, for either value of the coin: constructive interference on this small cycle concentrates the walk onto a single position after exactly 3 steps.
Open in Studio- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costO(k^(4/5) n^(9/5)) oracle queries to decide whether all k of the n × n matrices commute; the Zoo states that classically the task requires Ω(k n²) queries. The abstract separately states a lower bound of Ω(k^(1/2) n) for the problem, obtained with Ambainis's lower-bounding technique, so the two bounds the abstract gives do not meet.
- Papers1
Given oracle access to k matrices of size n × n, where a query names a matrix index x together with a pair of indices i, j and returns the ij entry of the x-th matrix, decide whether all k of the matrices commute with one another. The paper uses a theorem of Mario Szegedy that relates the hitting time of a classical random walk to that of a quantum walk, and it also takes a look at Ambainis's method of quantum walk, applying both walks to the triangle finding problem and to the matrix verification problem in order to compare the powers of the two different walks. The abstract reports that Szegedy's algorithm turns out to be generalizable to similar problems and that Szegedy's theorem is therefore the one the paper uses to analyze matrix set commutativity, and it states that the technique behind the upper bound is generalized to a broader range of similar problems. The paper also presents Ambainis's method of lower bounding technique in order to obtain a lower bound for this problem. The abstract records that this is probably the first problem to be studied on the quantum query complexity using quantum walks that involves more than one parameter, here k and n.
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 →
The paper uses a theorem of Mario Szegedy that relates the hitting time of a classical random walk to that of a quantum walk, and it also takes a look at Ambainis's method of quantum walk, applying both walks to the triangle finding problem and to the matrix verification problem in order to compare the powers of the two different walks. The abstract reports that Szegedy's algorithm turns out to be generalizable to similar problems and that Szegedy's theorem is therefore the one the paper uses to analyze matrix set commutativity, and it states that the technique behind the upper bound is generalized to a broader range of similar problems. The paper also presents Ambainis's method of lower bounding technique in order to obtain a lower bound for this problem. The abstract records that this is probably the first problem to be studied on the quantum query complexity using quantum walks that involves more than one parameter, here k and n. 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(k^(4/5) n^(9/5)) oracle queries to decide whether all k of the n × n matrices commute; the Zoo states that classically the task requires Ω(k n²) queries. The abstract separately states a lower bound of Ω(k^(1/2) n) for the problem, obtained with Ambainis's lower-bounding technique, so the two bounds the abstract gives do not meet..
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(k^(4/5) n^(9/5)) oracle queries to decide whether all k of the n × n matrices commute; the Zoo states that classically the task requires Ω(k n²) queries. The abstract separately states a lower bound of Ω(k^(1/2) n) for the problem, obtained with Ambainis's lower-bounding technique, so the two bounds the abstract gives do not meet.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity basis
- abstract of arXiv:quant-ph/0509206: "We give an O(k^{4/5}n^{9/5}) algorithm as well as a lower bound of Omega(k^{1/2}n)", with the technique named earlier in the same abstract, "We also present Ambainis's method of lower bounding technique (quant-ph/0002066) to obtain a lower bound for this problem"; Quantum Algorithm Zoo entry "Matrix Commutativity" (LaTeX rendered into Unicode): "this can be achieved on a quantum computer using O(k^(4/5)n^(9/5)) queries, whereas classically this requires Ω( k n² ) queries."
- 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: Commutativity testing of a matrix set by quantum walk
PROBLEM: Given oracle access to k matrices of size n × n, where a query names a matrix index x together with a pair of indices i, j and returns the ij entry of the x-th matrix, decide whether all k of the matrices commute with one another.
IDEA: The paper uses a theorem of Mario Szegedy that relates the hitting time of a classical random walk to that of a quantum walk, and it also takes a look at Ambainis's method of quantum walk, applying both walks to the triangle finding problem and to the matrix verification problem in order to compare the powers of the two different walks. The abstract reports that Szegedy's algorithm turns out to be generalizable to similar problems and that Szegedy's theorem is therefore the one the paper uses to analyze matrix set commutativity, and it states that the technique behind the upper bound is generalized to a broader range of similar problems. The paper also presents Ambainis's method of lower bounding technique in order to obtain a lower bound for this problem. The abstract records that this is probably the first problem to be studied on the quantum query complexity using quantum walks that involves more than one parameter, here k and n.
REPORTED COST: O(k^(4/5) n^(9/5)) oracle queries to decide whether all k of the n × n matrices commute; the Zoo states that classically the task requires Ω(k n²) queries. The abstract separately states a lower bound of Ω(k^(1/2) n) for the problem, obtained with Ambainis's lower-bounding technique, so the two bounds the abstract gives do not meet.
BASIS: abstract of arXiv:quant-ph/0509206: "We give an O(k^{4/5}n^{9/5}) algorithm as well as a lower bound of Omega(k^{1/2}n)", with the technique named earlier in the same abstract, "We also present Ambainis's method of lower bounding technique (quant-ph/0002066) to obtain a lower bound for this problem"; Quantum Algorithm Zoo entry "Matrix Commutativity" (LaTeX rendered into Unicode): "this can be achieved on a quantum computer using O(k^(4/5)n^(9/5)) queries, whereas classically this requires Ω( k n² ) queries."
PRIMARY SOURCE: Yuki Kelly Itakura (2005), Quantum Algorithm for Commutativity Testing of a Matrix Set — https://arxiv.org/abs/quant-ph/0509206
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
- Quantum Algorithm for Commutativity Testing of a Matrix Set
Yuki Kelly Itakura · 2005
Primary source: it applies Szegedy's theorem relating the hitting time of a classical random walk to that of a quantum walk to the commutativity of a matrix set, states the O(k^(4/5) n^(9/5)) algorithm quoted in the complexity field together with a lower bound of Ω(k^(1/2) n), and compares Szegedy's walk against Ambainis's on the triangle finding and matrix verification problems. Consult it for the walk the upper bound is built on and for which similar problems the generalized technique is claimed to cover.