dorsal/arxiv
View SchemaQuantum Algorithm for Commutativity Testing of a Matrix Set
| Authors | Yuki Kelly Itakura |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0509206 |
| URL | https://arxiv.org/abs/quant-ph/0509206 |
Abstract
Suppose we have k matrices of size n by n. We are given an oracle that knows all the entries of k matrices, that is, we can query the oracle an (i,j) entry of the l-th matrix. The goal is to test if each pair of k matrices commute with each other or not with as few queries to the oracle as possible. In order to solve this problem, we use a theorem of Mario Szegedy (quant-ph/0401053) that relates a hitting time of a classical random walk to that of a quantum walk. We also take a look at another method of quantum walk by Andris Ambainis (quant-ph/0311001). We apply both walks into triangle finding problem (quant-ph/0310134) and matrix verification problem (quant-ph/0409035) to compare the powers of the two different walks. We also present Ambainis's method of lower bounding technique (quant-ph/0002066) to obtain a lower bound for this problem. It turns out Szegedy's algorithm can be generalized to solve similar problems. Therefore we use Szegedy's theorem to analyze the problem of matrix set commutativity. We give an O(k^{4/5}n^{9/5}) algorithm as well as a lower bound of Omega(k^{1/2}n). We generalize the technique used in coming up with the upper bound to solve a broader range of similar problems. 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.
{
"annotation_id": "054f69af-3b30-4a25-a91d-115309980b6d",
"date_created": "2026-03-02T18:02:20.478000Z",
"date_modified": "2026-03-02T18:02:20.478000Z",
"file_hash": "f0f9b29cccadd8b7eacefd9d5ef98f2d1802027fdcfde5c46cefe71dacb63761",
"private": false,
"record": {
"abstract": "Suppose we have k matrices of size n by n. We are given an oracle that knows\nall the entries of k matrices, that is, we can query the oracle an (i,j) entry\nof the l-th matrix. The goal is to test if each pair of k matrices commute with\neach other or not with as few queries to the oracle as possible. In order to\nsolve this problem, we use a theorem of Mario Szegedy (quant-ph/0401053) that\nrelates a hitting time of a classical random walk to that of a quantum walk. We\nalso take a look at another method of quantum walk by Andris Ambainis\n(quant-ph/0311001). We apply both walks into triangle finding problem\n(quant-ph/0310134) and matrix verification problem (quant-ph/0409035) to\ncompare the powers of the two different walks. We also present Ambainis\u0027s\nmethod of lower bounding technique (quant-ph/0002066) to obtain a lower bound\nfor this problem. It turns out Szegedy\u0027s algorithm can be generalized to solve\nsimilar problems. Therefore we use Szegedy\u0027s theorem to analyze the problem of\nmatrix set commutativity. We give an O(k^{4/5}n^{9/5}) algorithm as well as a\nlower bound of Omega(k^{1/2}n). We generalize the technique used in coming up\nwith the upper bound to solve a broader range of similar problems. This is\nprobably the first problem to be studied on the quantum query complexity using\nquantum walks that involves more than one parameter, here, k and n.",
"arxiv_id": "quant-ph/0509206",
"authors": [
"Yuki Kelly Itakura"
],
"categories": [
"quant-ph"
],
"title": "Quantum Algorithm for Commutativity Testing of a Matrix Set",
"url": "https://arxiv.org/abs/quant-ph/0509206"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "02219a50-9deb-417f-a916-897e2a994136",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}