A sparse simulator represents a quantum state by storing only its nonzero amplitudes and their associated basis states. It is most effective when a program allocates many qubits but manipulates relatively few basis states, avoiding the full-state representation that stores every amplitude. section 8.1 section 8.5
This advantage depends on state structure, not qubit count alone. Reversible computations often remain sparse: extra qubits hold intermediate results without increasing the number of basis states. Grover’s algorithm can therefore be suitable for sparse simulation when its oracle is implemented as reversible computation. section 8.1 section 8.5
When assessing a sparse-simulator run, track:
- The total qubits allocated, program length, and number of basis states present in superposition during execution. section 8.5
- Whether phase kickback or other operations temporarily increase the number of manipulated basis states. section 8.1
- Whether simulator timing reflects classical simulation cost rather than expected quantum-hardware runtime. section 9.3
N queens simulator comparison
Two Grover-based N queens implementations can differ sharply on a full-state Qiskit simulator because allocated qubits strongly affect its runtime. On a sparse Q# simulator, their times can be similar when both manipulate the same number of basis states. section 9.3
Table 9.1 Simulation times for different solutions to the N queens puzzle
| Algorithm | Qiskit run time | Q# run time |
| Section 8.2 | 137 sec | 16 sec |
| Section 8.3 | < 1 sec | 20 sec |
Compare measured times for two N queens solutions across a full-state Qiskit simulator and a sparse Q# simulator. section 9.3
