Simulating and Verifying Quantum Circuits

Hello! Welcome to the final lesson of the "Quantum Computing Foundations" module.

Over the last six lessons, we've built a solid foundation, moving from the representation of single qubits to the application of single- and two-qubit gates, the intricacies of measurement, and the uniquely quantum phenomenon of entanglement, which we explored through the Bell states.

Today, we will bring all these concepts together in a practical context. The learning outcome for this lesson is to implement quantum circuits in a simulator and verify the correctness by comparing measured state statistics with exact quantum predictions.

This lesson will bridge theory and practice. We will explore:

1. The core algorithms that power a state-vector quantum circuit simulator.
2. The process of simulating measurement and collecting statistics.
3. A concrete example of simulating a circuit and verifying its output against the expected theoretical predictions.
4. The challenges of verifying quantum states at scale, providing a glimpse into current research frontiers.

Given your background in implementing numerical simulations, we will focus on the algorithmic details behind building a simulator from first principles.

1. The Engine of a Quantum Simulator

A state-vector simulator is the most straightforward type of quantum simulator. It tracks the complete quantum state of the system, represented as a vector of $2^n$ complex amplitudes for an $n$-qubit system. Applying a quantum gate corresponds to multiplying this state vector by the gate's unitary matrix.

While one could construct the full $2^n\times 2^n$ unitary matrix for a given gate operation and multiply it by the state vector, this is highly inefficient. A more sophisticated approach involves algorithms that update the state vector directly, exploiting the sparse structure of the gate matrices.

The following resource provides an excellent, in-depth guide to the algorithms needed to build a simulator from scratch. It is written for an audience with a programming and computer science background, so it should align well with your experience.

To summarize the key ideas from the paper:

• State Evolution: Instead of building large, sparse unitary matrices, algorithms like qubitWiseMultiply directly calculate the effect of a gate on the state vector's amplitudes. For a gate on qubit i, the algorithm cleverly pairs up amplitudes whose indices differ only in the i-th bit and applies the 2x2 gate matrix to these pairs. This is the core of an efficient state-vector simulator.
• Measurement Simulation: As discussed in Section 7 of the paper, measurement is non-unitary. The most common simulation method that mimics a real quantum computer is probabilistic collapse. After computing the final state vector $|\psi ⟩={\sum }_i{c}_i|i⟩$, you:
  1. Calculate the probability of each outcome: $P(i)=|c_i{|}^2$.
  2. Perform a weighted random sampling based on these probabilities to get a single classical bit string.
  3. To get statistics, you repeat this entire process (running the circuit simulation from the start) for a desired number of "shots".

2. A Practical Example: Simulate and Verify

Let's walk through the process for a circuit we've seen before: generating the Bell state $|{\Phi }^{+}⟩$. The circuit starts with $|00⟩$, applies a Hadamard gate to qubit 0, and then a CNOT gate with qubit 0 as control and qubit 1 as target.

Step 1: Calculate Exact Quantum Predictions

First, we determine the final state vector analytically.

1. Initial State: $|{\psi }_0⟩=|00⟩$, which corresponds to the state vector $[1,0,0,0{]}^T$.
2. Apply Hadamard on Qubit 0: The operation is $H\otimes I$. $$|{\psi }_1⟩=(H\otimes I)|{\psi }_0⟩=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\otimes \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=\frac{1}{\sqrt{2}}\left(\begin{array}{cccc}1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& -1& 0\\ 0& 1& 0& -1\end{array}\right)\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}1/\sqrt{2}\\ 0\\ 1/\sqrt{2}\\ 0\end{array}\right)$$ This corresponds to the state $\frac{1}{\sqrt{2}}(|00⟩+|10⟩)$.
3. Apply CNOT(0,1): $$|{\psi }_2⟩={\text{CNOT}}_{01}|{\psi }_1⟩=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}1/\sqrt{2}\\ 0\\ 1/\sqrt{2}\\ 0\end{array}\right)=\left(\begin{array}{c}1/\sqrt{2}\\ 0\\ 0\\ 1/\sqrt{2}\end{array}\right)$$ This is our final state vector, corresponding to $|{\Phi }^{+}⟩=\frac{1}{\sqrt{2}}(|00⟩+|11⟩)$.

From this final state vector, the exact probabilities for measurement outcomes in the computational basis are:

• $P(00)=|1/\sqrt{2}{|}^2=0.5$
• $P(01)=|0{|}^2=0$
• $P(10)=|0{|}^2=0$
• $P(11)=|1/\sqrt{2}{|}^2=0.5$

Step 2: Simulate and Measure

Now, we use our simulator's logic.

1. Initialize the state vector to $[1,0,0,0{]}^T$.
2. Call a function like qubitWiseMultiply with the Hadamard matrix for qubit 0. The state vector becomes $[1/\sqrt{2},0,1/\sqrt{2},0{]}^T$.
3. Call qubitWiseMultiply again with the Pauli-X matrix for qubit 1, but with a control on qubit 0. The state vector becomes $[1/\sqrt{2},0,0,1/\sqrt{2}{]}^T$.
4. Now, simulate a single "shot". Calculate the probabilities (0.5, 0, 0, 0.5) and sample from this distribution. You might get '00'.
5. Repeat steps 1-4 for, say, 1024 shots. You would expect to record approximately 512 outcomes of '00' and 512 outcomes of '11'.

Step 3: Verify Correctness

The final step is to compare the measured statistics from the simulation with the exact predictions.

If the simulated frequencies closely match the exact probabilities (within expected statistical noise), we have verified the correctness of our circuit implementation. This exact loop of "predict, simulate, compare" is fundamental to developing and debugging quantum algorithms.

The following paper demonstrates this principle for more complex algorithms like quantum teleportation and error correction, showing plots that compare expected (analytical) and observed (simulated) outcomes.

3. The Verification Challenge at Scale

The method we just discussed works perfectly for a small number of qubits, where we can classically compute the exact $2^n$ state vector. But what happens when $n$ is large (e.g., $n>50$)? The memory and time required to compute the exact state vector become prohibitive. This is, after all, the basis for quantum advantage.

This raises a critical question: How can you verify that a real quantum computer is producing the correct state if you can't classically compute the answer to check against?

This is the problem of quantum state certification or verification, a major area of research. Standard methods have significant drawbacks.

As the video explains, simple approaches are often insufficient. For example, cross-entropy benchmarking, famously used by Google to claim quantum supremacy, primarily checks the probability distribution of the output states (the diagonal elements of the density matrix). It can fail to detect coherent errors that affect the phases (the off-diagonal elements), which are crucial for many quantum algorithms. The video goes on to propose a more robust method based on "classical shadows," which is an example of the cutting-edge work in this field.

On a related note, the classical simulation of quantum systems is itself an active research area. While we focused on state-vector simulation, which is ideal for finding exact probabilities, other methods are optimized for different tasks. For instance, if the goal is only to sample from the output distribution (not to know all the amplitudes), more advanced algorithms exist that can be more efficient under certain conditions, such as memory limitations.

The video below introduces one such alternative, contrasting the standard "qubit-by-qubit" sampling method (which requires computing difficult marginal probabilities) with a more efficient "gate-by-gate" approach for circuit simulation.

Conclusion

This lesson concludes our foundational module by grounding our theoretical knowledge in the practical task of simulation and verification.

Key Takeaways:

• State-vector simulators represent the quantum state as a $2^n$ vector of complex amplitudes.
• Efficient simulators use algorithms like qubitWiseMultiply to apply gates in $O(2^n)$ time, avoiding the construction of enormous matrices.
• Measurement is simulated probabilistically. To obtain statistics, the entire circuit simulation is run for many "shots".
• Verification for small circuits involves comparing the simulated measurement statistics against the exact probabilities derived from the analytically computed final state vector.
• Verifying the output of large-scale quantum computations is a major challenge, as classical simulation is intractable. This has spurred research into advanced techniques like quantum state certification.

Preview of the Next Module:

You have now completed the "Quantum Computing Foundations" module. You have a comprehensive understanding of the essential components of quantum computation. In our next module, "Foundational Quantum Algorithms," we will put this knowledge to use. We will begin by implementing and analyzing the Deutsch-Jozsa algorithm, one of the first and simplest demonstrations of a quantum speedup. The simulation and verification techniques we discussed today will be our primary tools for exploring how these algorithms work.