Quantum algorithms must be simulated on classical computers to validate correct behavior, but this looks very different from classical logic simulation. Paul Cunningham (GM, Verification at Cadence), Raúl Camposano (Silicon Catalyst, entrepreneur, former Synopsys CTO and lecturer at Stanford, EE292A) and I continue our series on research ideas. As always, feedback welcome.
The Innovation
This month’s pick is How to Write a Simulator for Quantum Circuits from Scratch: A Tutorial. The authors are from École de Technologie Supérieure, Montreal and the University of Massachusetts. The paper was posted in June 2025 in arXiv.
Quantum simulators work on an abstraction – how qubits and “gates” are implemented is a fascinating topic but a distraction for this discussion. Our goal in this review is to introduce the topic of simulating quantum algorithms on a classical computer, because these methods are sufficiently disjoint from familiar classical computation to require an introduction before we move onto new research in this area.
This paper introduces a method to build a simulator for a small quantum computer (~20 qubits). It is supported by a web-based implementations and code walkthroughs to give a sense of how quantum simulation works. You should think of linear algebra methods to evaluate a circuit, multiplying an initial qubit vector by a series of tensors corresponding to gates in the circuit.
Paul’s view
Quantum venture funding is already well over $3B, rising fast and getting a lot of attention in the media. So what about verifying quantum circuits? First stop here is a quantum circuit simulator. Kudos to Bernard for finding a wonderfully written paper on this topic. It describes notations used for describing quantum circuits, both graphically and in equation form. It also works through the basic math needed to understand how a quantum simulator works. It’s an algorithmic level paper, not a paper on quantum physics.
In a digital circuit, each “bit” of state (a register or a wire) can be read and written independently. Logic simulators need to process transitions on registers and wires in time order, via an event queue, but this processing is local and need only consider the gates they are directly connected to.
In the quantum world “qu-bits” of state are “entangled” and need to be considered collectively as a single “state vector”. Simulating a quantum circuit proceeds like an analog circuit simulation where a vector of all the voltages or currents on each wire is formed, and simulation involves multiplying this vector with a matrix whose coefficients are determined by the circuit components and connectivity. For a circuit with n wires an analog simulator must multiply a 1 x n circuit state vector by an n x n simulation matrix derived from the circuit structure.
The cool thing about a quantum circuit is that a circuit with n qubits has a state vector with 2^n elements, one for each of the 2^n binary representations of n-bits. A quantum circuit performs operations simultaneously on all 2^n elements of this state vector, with means it conceptually operates in parallel on all 2^n possible values of the n qubits.
To simulate a quantum circuit with non-quantum digital hardware means multiplying a quantum state vector of size 2^n by a simulation matrix of size 2^n x 2^n, which is O(4^n) multiplications. The paper works through some neat algorithmic tricks based on some fundamental properties of quantum state vectors and simulation matrices that improves the runtime complexity to O(n.2^n). The elements of the state vector are floating point numbers, so the entire simulation maps very well to GPUs, e.g. this NVIDIA blog claims evaluating up to 36 qubits using eight A100s. Wow!
Each element in the state vector is a complex number, whose magnitude squared is the probability of the circuit being in that state. The sum of all the magnitude squared across the whole state vector is 1 and you can think of the state vector as representing a point on the surface of a 2^n dimensional hypersphere whose radius is 1. The goal of a typical quantum circuit algorithm is to use quantum gates to move the state vector around this hypersphere until it points almost perfectly along the axis of the dimension that is the desired result of the algorithm. Logic gates in digital circuits perform Boolean operations on state bits to calculate their result. Quantum gates rotate state vectors in various ways around their hypersphere. Developing a quantum algorithm requires figuring out a combination of rotational operations that move the state vector towards the desired result. Let’s see what Bernard can find published on what it means to verify these kinds of algorithm.
Raúl’s view
This month’s paper is a very nice, detailed tutorial on how to build a quantum circuit simulator using classical computing techniques, even with minimal prior knowledge of quantum mechanics. A simulator is verification 101; the purpose of creating a simulator from scratch is not as an alternative to existing open-source and commercial packages, but for a deeper understanding of quantum computing and the core algorithms necessary. It introduces essential quantum concepts and notations such as Dirac notation, state vectors, Hilbert space, tensor products, and the Bloch sphere, and quantum gates such as Hadamard, SWAP, Toffoli (CCNOT), Pauli X, Y and Z. Unlike physical quantum computers which collapse the state to 0 or 1 when measured, simulators can directly compute the complete state, including the probability of a 1 and the phase (Bloch sphere coordinates of each qubit). Measurement gates collapse the state and result in two new state vectors, corresponding to a measurement of 0 and 1.
The resulting simulator can handle up to ~20 qubits on a personal computer, utilizing roughly 1000–2000 lines of code in JavaScript (the largest quantum computer than can be simulated on a HPC is 50 qubits). An emphasis is placed on efficiency to handle the computational complexity associated with explicit matrix multiplication, in particular for Qubit-Wise Multiplication without explicitly forming the large layer matrices, but still O(2n nd) for d layers with n gates each; and SWAP, the exchange of the states of qubits simulated by directly manipulating the indices of the state vector’s amplitudes, also exponential in complexity. Further enhancements mentioned include adding robust error checking, implementing memory-saving in-place updates, and leveraging hardware acceleration via GPU programming.
I found the paper a great introduction to quantum computing. The online simulators help explain the basics, and the paper references commercial systems and more advanced research for readers interested in more detail.
Share this post via:
Quantum Computing Technologies and Challenges