dorsal/arxiv
View SchemaOn the simulation of quantum circuits
| Authors | Richard Jozsa |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0603163 |
| URL | https://arxiv.org/abs/quant-ph/0603163 |
Abstract
We consider recent works on the simulation of quantum circuits using the formalism of matrix product states and the formalism of contracting tensor networks. We provide simplified direct proofs of many of these results, extending an explicit class of efficiently simulable circuits (log depth circuits with 2-qubit gates of limited range) to the following: let C be any poly sized quantum circuit (generally of poly depth too) on n qubits comprising 1- and 2- qubit gates and 1-qubit measurements (with 2-qubit gates acting on arbitrary pairs of qubit lines). For each qubit line j let D_j be the number of 2-qubit gates that touch or cross the line j i.e. the number of 2-qubit gates that are applied to qubits i,k with i \leq j \leq k. Let D=max_j D_j. Then the quantum process can be classically simulated in time n poly(2^D). Thus if D=O(log n) then C may be efficiently classically simulated.
{
"annotation_id": "017b37fc-0112-4f74-99b3-086e3830dd56",
"date_created": "2026-03-02T18:02:23.718000Z",
"date_modified": "2026-03-02T18:02:23.718000Z",
"file_hash": "bc9ba8e6526a13f2fb3e9a670068add95a6c6f5e34568fed76f11a19e4ede510",
"private": false,
"record": {
"abstract": "We consider recent works on the simulation of quantum circuits using the\nformalism of matrix product states and the formalism of contracting tensor\nnetworks. We provide simplified direct proofs of many of these results,\nextending an explicit class of efficiently simulable circuits (log depth\ncircuits with 2-qubit gates of limited range) to the following: let C be any\npoly sized quantum circuit (generally of poly depth too) on n qubits comprising\n1- and 2- qubit gates and 1-qubit measurements (with 2-qubit gates acting on\narbitrary pairs of qubit lines). For each qubit line j let D_j be the number of\n2-qubit gates that touch or cross the line j i.e. the number of 2-qubit gates\nthat are applied to qubits i,k with i \\leq j \\leq k. Let D=max_j D_j. Then the\nquantum process can be classically simulated in time n poly(2^D). Thus if\nD=O(log n) then C may be efficiently classically simulated.",
"arxiv_id": "quant-ph/0603163",
"authors": [
"Richard Jozsa"
],
"categories": [
"quant-ph"
],
"title": "On the simulation of quantum circuits",
"url": "https://arxiv.org/abs/quant-ph/0603163"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e4bafa0e-8e7a-4fad-b509-8d1d56edd74f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}