{ "id": "epj9vqd2js", "slug": "quantum-circuit-simulation", "title": "Quantum circuit simulation", "updated": "2026-09-30", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.algorithms" } ], "geo": [ { "id": "geo.nongeo.t2001.technology.computing.ai.algorithms", "label": "Non-geographic · 2001 to 2020: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t2001", "label": "Non-geographic · 2001 to 2020", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001" }, { "id": "geo.nongeo.t2001.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology" }, { "id": "geo.nongeo.t2001.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing" }, { "id": "geo.nongeo.t2001.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai" }, { "id": "geo.nongeo.t2001.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.algorithms" } ] } ], "excerpt": "Quantum circuit simulation is the classical computation of quantum circuit outputs; an N-qubit state vector needs 2^N amplitudes, so a 16 GB machine caps out near 30 qubits.", "snippet": "Quantum circuit simulation is the classical computation of quantum circuit outputs; an N-qubit state vector needs 2^N amplitudes, so a 16 GB machine caps out near 30 qubits.", "node": "technology.computing.ai.algorithms", "markdown": "# Quantum circuit simulation\n\nQuantum circuit simulation is the classical computation of quantum circuit outputs, and its central obstacle is exponential scaling: an N-qubit state vector holds \\( 2^{N} \\) complex amplitudes, so a 16 GB machine caps out near 30 qubits, and a dense unitary on N qubits would require \\( 4^{N} \\) complex entries.[1](https://arxiv.org/html/2311.16505) • [2](https://who.paris.inria.fr/Andre.Chailloux/QCLGLectureNotes.pdf)\n\n| Key fact | Value |\n|---|---|\n| State-vector memory | \\( 8 \\cdot 2^{n} \\) bytes[3](https://quantumai.google/qsim/choose_hw) |\n| State-vector runtime | Proportional to \\( g \\cdot 2^{n} \\), where g is the number of two-qubit gates[4](http://github.com/quantumlib/qsim) |\n| Largest distributed state-vector benchmark cited | 38 qubits over up to 2048 compute nodes (QuEST)[5](https://doi.org/10.1038/s41598-019-47174-9) |\n| Largest tensor-network verification cited | 53-qubit Sycamore random circuit sampling, 8435 A100 GPU hours for \\( 2^{20} \\) bitstrings[6](https://arxiv.org/html/2310.03978) |\n| Efficient special case | Stabilizer (Clifford) circuits, polynomial time by the Gottesman–Knill theorem[7](https://www.rintonpress.com/xxqic10/qic-10-34/0258-0271.pdf) |\n| Hardness limit | Computing outputs of random quantum circuits is #P-hard[8](https://www.nature.com/articles/s41567-023-02131-2) |\n| Noisy-circuit sampling record cited | 476-qubit ideal and noisy QAOA circuits (Pilot-Wave Simulator)[9](https://quantum-journal.org/papers/q-2026-07-23-2173/) |\n\n## How it works\n\nA quantum circuit has three stages: initialization of all qubits in the |0⟩ state, a set of gates representing unitary transformations, and a final layer of measurements in the computational basis.[10](https://www.cl.cam.ac.uk/teaching/2324/Quantum_Computing_Lecture_5_2024.pdf) In the state-vector (Schrödinger-style) representation, the joint state of n qubits is a vector of \\( 2^{n} \\) complex amplitudes. Composition across wires is achieved by the tensor product, while composition along wires is achieved by the ordinary matrix product applied right to left.[10](https://www.cl.cam.ac.uk/teaching/2324/Quantum_Computing_Lecture_5_2024.pdf) A general unitary on n qubits is a \\( 2^{n} \\times 2^{n} \\) matrix.[2](https://who.paris.inria.fr/Andre.Chailloux/QCLGLectureNotes.pdf)\n\nEvery circuit can also be represented as a tensor network, and the simulator's job becomes contracting that network to obtain the amplitudes of specific final bitstrings.[11](http://preview-www.nature.com/articles/s41534-019-0196-1.pdf) • [6](https://arxiv.org/html/2310.03978) The cost of a contraction is governed by the chosen contraction path; the tree-width (a graph-structure measure bounding how hard a network is to decompose) of the circuit graph bounds it, and circuits with logarithmic tree-width can be simulated deterministically in polynomial time.[1](https://arxiv.org/html/2311.16505)\n\nA third family exploits structure: the [Gottesman–Knill theorem](https://www.edgepedia.org/gottesman-knill-theorem) states that a stabilizer circuit, one consisting solely of CNOT, Hadamard, and phase gates, can be simulated efficiently on a classical computer, so each uniform family of Clifford circuits provides no exponential speed-up over classical computation.[7](https://www.rintonpress.com/xxqic10/qic-10-34/0258-0271.pdf)\n\n## How it is done\n\nA practitioner's workflow mirrors the circuit definition. First, allocate and initialize the state: \\( 2^{n} \\) amplitudes for a state vector, or a compact representation for stabilizer or tensor-network methods. Second, apply the gate layers in order, updating the representation after each gate; in state-vector simulators this means touching all \\( 2^{n} \\) amplitudes per gate, giving total runtime proportional to \\( g \\cdot 2^{n} \\) for g two-qubit gates.[4](http://github.com/quantumlib/qsim) Third, produce output: the full state vector, selected amplitudes, samples of bitstrings, or expectation values. For sampling circuits with measurement gates, simulators draw bitstrings from the final distribution.[3](https://quantumai.google/qsim/choose_hw)\n\nWhen the state vector cannot be stored, as above roughly 50 qubits, tensor-network simulations instead compute amplitudes of small bitstring sets and use importance sampling or rejection sampling, with the bitstrings' probabilities, to emulate the measurement process.[6](https://arxiv.org/html/2310.03978)\n\n## Origin\n\nThe stabilizer lineage is anchored by [Scott Aaronson](https://www.edgepedia.org/scott-aaronson) and [Daniel Gottesman](https://www.edgepedia.org/daniel-gottesman)'s 2004 [Physical Review A](https://www.edgepedia.org/physical-review-a) paper \"Improved simulation of stabilizer circuits\", which gave a tableau algorithm faster than the one directly implied by the Gottesman–Knill theorem: by removing the need for Gaussian elimination, measurements are simulated in \\( O(n^{2}) \\) steps instead of \\( O(n^{3}) \\).[12](https://doi.org/10.1103/physreva.70.052328) They implemented it in the freely available CHP (CNOT-Hadamard-phase) program, which can handle thousands of qubits easily, at the cost of a factor of 2 increase in the bits needed to represent a state.[12](https://doi.org/10.1103/physreva.70.052328) The same paper shows that simulating stabilizer circuits is complete for the classical complexity class ⊕L and extends the algorithm to mixed states, circuits with a limited number of non-Clifford gates, and general tensor-product initial states.[12](https://doi.org/10.1103/physreva.70.052328)\n\nTwo further platform papers mark the modern tooling era. Tyson Jones and colleagues presented QuEST in [Scientific Reports](https://www.edgepedia.org/scientific-reports) in 2019.[5](https://doi.org/10.1038/s41598-019-47174-9) Sergey Bravyi and colleagues published the low-rank stabilizer decomposition method on arXiv in 2018.[13](https://doi.org/10.48550/arxiv.1808.00128)\n\n## Variants\n\n**State vector.** The exact Schrödinger-style approach computes all \\( 2^{n} \\) amplitudes. Google's qsim is a C++ implementation of this method; with 16 GB of RAM it can simulate 30 qubits, and RAM usage doubles with each additional qubit.[1](https://arxiv.org/html/2311.16505) [Performance](https://www.edgepedia.org/performance) techniques include gate fusion, single-precision arithmetic, AVX/FMA vectorization, and OpenMP multithreading.[4](http://github.com/quantumlib/qsim)\n\n**Tensor networks.** Contraction-based simulators such as qFlex compute exact amplitudes of random quantum circuits without ever storing the full state.[11](http://preview-www.nature.com/articles/s41534-019-0196-1.pdf) Matrix-product-state (MPS) variants exploit low entanglement: Qiskit's MPS simulator is described as optimal for weakly entangled states and supports ideal modeling up to 100 qubits.[1](https://arxiv.org/html/2311.16505) A [tree tensor network](https://www.edgepedia.org/tree-tensor-network) algorithm first determines a fixed tree structure adapted to the expected entanglement generated by the circuit, then applies gates by absorbing single-qubit gates into leaf nodes and splitting two-qubit gates.[14](https://quantum-journal.org/papers/q-2023-03-30-964/) Stabilizer tensor networks generalize the tableau formalism used for Clifford circuit simulation, with proven update rules for Clifford gates, non-Clifford gates, and measurements.[15](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.133.230601) Decision-diagram methods are represented by the freely available QuIDDPro package.[16](https://link.springer.com/book/10.1007/978-90-481-3065-8)\n\n**Hybrid stabilizer methods.** The Feynman path method has a time cost of \\( O(4^{m}) \\) and memory cost \\( O(m + n) \\), where m is the number of gates and n the number of qubits; the SPIR method costs \\( O(n^{3}(2 \\cdot d_{\\mathrm{nc}})^{k}) \\) time and \\( O(n \\log d_{\\mathrm{nc}}) \\) memory, with inner products between stabilizer states taking \\( O(n^{3}) \\) time.[1](https://arxiv.org/html/2311.16505)\n\n**GPU and distributed engines.** QuEST is described as the first open-source hybrid multithreaded and distributed, GPU-accelerated simulator of universal quantum circuits; its GPU implementation offers speedups of about \\( 5\\times \\) over an already highly parallelized 24-threaded single-node simulation.[5](https://doi.org/10.1038/s41598-019-47174-9) NVIDIA's cuQuantum SDK provides cuStateVec for state-vector simulation and cuTensorNet for tensor-network contraction on GPUs.[1](https://arxiv.org/html/2311.16505) Qiskit Aer's tensor-network method is GPU-accelerated through cuTensorNet,[17](https://qiskit.github.io/qiskit-aer/stubs/qiskit_aer.AerSimulator.html) and the cuQuantum Appliance integrates the cusvaer distributed engine into Qiskit Aer for multi-node simulation without source-code modifications.[18](https://docs.nvidia.com/cuda/cuquantum/latest/appliance/qiskit.html) For sampling bitstrings, qsim's documentation states that the cuQuantum backend performs significantly better than qsim's native GPU backend and is needed for multi-GPU support.[3](https://quantumai.google/qsim/choose_hw)\n\n## Applications\n\nTensor-network simulation on NVIDIA A100 GPUs was used to verify random circuit sampling experiments based on 53-qubit 18-cycle Sycamore circuits with \\( 2^{20} \\) sampled bitstrings, using 8435 GPU hours, 3.96 times faster than a non-optimized version.[6](https://arxiv.org/html/2310.03978) The Jet open-source tensor-network simulator can efficiently simulate up to 53 qubits at circuit depth 10 through slicing, solving a single amplitude output of a Sycamore-53 benchmark in 0.76 seconds at depth 10.[1](https://arxiv.org/html/2311.16505) Beyond supremacy experiments, simulators generate samples from ideal and noisy QAOA circuits; the Pilot-Wave Simulator combines tensor-network techniques with a Markov process in which a classical state evolves according to the local structure of the quantum circuit, targeting QAOA circuits with up to 476 qubits.[9](https://quantum-journal.org/papers/q-2026-07-23-2173/)\n\n## Limitations and alternatives\n\n**Exponential scaling.** The state-vector method's memory rule of thumb is \\( 8 \\cdot 2^{n} \\) bytes, and noiseless runtime grows as \\( 2^{n} \\); noisy simulation grows as \\( 2^{n} \\) multiplied by the number of iterations, with runtime growing linearly with circuit depth beyond 20 qubits.[3](https://quantumai.google/qsim/choose_hw) Because the state vector cannot be stored for more than 50 qubits, larger circuits require tensor-network sampling workarounds.[6](https://arxiv.org/html/2310.03978)\n\n**Contraction-path difficulty.** Identifying an optimal contraction path is an immensely challenging combinatorial optimization problem with no known efficient heuristic algorithm, though recent graph-partitioning, simulated-annealing-like, and architecture-aware methods have reduced the original 10,000-year estimate for a 53-qubit, 20-cycle Sycamore circuit to a duration comparable to the quantum experiments themselves.[6](https://arxiv.org/html/2310.03978)\n\n**Fundamental hardness.** [Computing](https://www.edgepedia.org/computing) outputs of random quantum circuits is #P-hard for any classical computer, with results extended to instantaneous quantum polynomial-time (IQP) circuits via a worst-case to average-case reduction.[8](https://www.nature.com/articles/s41567-023-02131-2) This bounds what any exact simulator can do on generic circuits.\n\nPublished comparisons do not settle several open questions: gate-throughput figures for the main engines, quantified noise-modeling fidelity limits, and head-to-head benchmarks against post-2023 quantum hardware.\n\n## References\n\n1. [Simulating Quantum Computations on Classical Machines: A Survey (Nov 2023)](https://arxiv.org/html/2311.16505)\n2. [Quantum Circuits and Logic Gates (lecture notes)](https://who.paris.inria.fr/Andre.Chailloux/QCLGLectureNotes.pdf)\n3. [Choosing hardware for your qsim simulation | Google Quantum AI](https://quantumai.google/qsim/choose_hw)\n4. [quantumlib/qsim](http://github.com/quantumlib/qsim)\n5. [Tyson Jones and colleagues (2019). QuEST and High Performance Simulation of Quantum Computers. Scientific Reports.](https://doi.org/10.1038/s41598-019-47174-9)\n6. [Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs](https://arxiv.org/html/2310.03978)\n7. [Quantum Information & Computation article on Clifford circuit simulation](https://www.rintonpress.com/xxqic10/qic-10-34/0258-0271.pdf)\n8. [The hardness of random quantum circuits](https://www.nature.com/articles/s41567-023-02131-2)\n9. [Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits](https://quantum-journal.org/papers/q-2026-07-23-2173/)\n10. [Quantum Computing (CST Part II) - Lecture 5: The Quantum Circuit Model](https://www.cl.cam.ac.uk/teaching/2324/Quantum_Computing_Lecture_5_2024.pdf)\n11. [qFlex: a flexible tensor-network quantum circuit simulator (npj Quantum Information)](http://preview-www.nature.com/articles/s41534-019-0196-1.pdf)\n12. [Scott Aaronson, Daniel Gottesman (2004). Improved simulation of stabilizer circuits. Physical Review A.](https://doi.org/10.1103/physreva.70.052328)\n13. [Bravyi, Sergey and colleagues (2018). Simulation of quantum circuits by low-rank stabilizer decompositions. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1808.00128)\n14. [Simulating quantum circuits using tree tensor networks](https://quantum-journal.org/papers/q-2023-03-30-964/)\n15. [Stabilizer Tensor Networks: Universal Quantum Simulator on a Basis of Stabilizer States](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.133.230601)\n16. [Quantum Circuit Simulation (Springer book)](https://link.springer.com/book/10.1007/978-90-481-3065-8)\n17. [AerSimulator - Qiskit Aer 0.17.1](https://qiskit.github.io/qiskit-aer/stubs/qiskit_aer.AerSimulator.html)\n18. [Qiskit, NVIDIA cuQuantum](https://docs.nvidia.com/cuda/cuquantum/latest/appliance/qiskit.html)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/quantum-circuit-simulation", "markdown_url": "https://www.edgepedia.org/quantum-circuit-simulation.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Quantum circuit simulation\", Edgepedia (EdgeChat), https://www.edgepedia.org/quantum-circuit-simulation. Edgepedia Community License 1.0.", "credit_md": "\"[Quantum circuit simulation](https://www.edgepedia.org/quantum-circuit-simulation)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/quantum-circuit-simulation](https://www.edgepedia.org/quantum-circuit-simulation). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Quantum circuit simulation\", Edgepedia (EdgeChat), https://www.edgepedia.org/quantum-circuit-simulation. Edgepedia Community License 1.0.", "speakable": "Quantum circuit simulation is the classical computation of quantum circuit outputs; an N-qubit state vector needs 2^N amplitudes, so a 16 GB machine caps out near 30 qubits." }