SparQSim Architecture

This document describes the overall architecture of the SparQSim repository (the home of the SparQ framework), the division of work between repositories, and the core modules. For a hands-on introduction, start with the Quick Start instead.

Overview

Project Goals

SparQ is a high-performance simulator framework for simulating quantum random access memory (QRAM) and sparse-state quantum computing. It aims to provide quantum-algorithm researchers and developers with:

  • Tools for efficiently simulating large-scale quantum systems (leveraging the sparse-state representation)

  • Accurate modeling of QRAM circuit behavior and noise effects

  • A register-level programming paradigm: perform arithmetic and logic directly on integer/Boolean registers, with no manual decomposition into gates

  • A complete algorithm library (Grover, Shor, state preparation, block encoding, Hamiltonian simulation, discrete adiabatic QDA, etc.)

  • A clean Python API (pysparq, see the API reference) for rapid prototyping

Repository Split

Dependency direction: SparQSim → QRAM-Simulator. This repository hosts the SparQ C++ framework (SparQ/ sparse-state simulator + SparQ_Algorithm/ algorithm library + all Python bindings and algorithm-style experiments); the QRAM base (Common + QRAM + ThirdParty) is released independently in the QRAM-Simulator repository, and this repository references and builds it as a git submodule (relative URL ../QRAM-Simulator.git).

Directory Layout

SparQSim/
├── SparQ/                  # SparQ C++ sparse-state simulator (the umbrella target SparQ is defined in the root CMake)
│   ├── include/            # public API headers (incl. cuda/ GPU backend, currently masked out by CMake)
│   └── src/                # implementation (incl. src/cuda/ GPU kernels)
├── SparQ_Algorithm/        # high-level algorithm C++ library
│   ├── include/            # grover / shor / state preparation / block encoding / Hamiltonian simulation / QDA
│   └── src/
├── PySparQ/                # pybind11 rich bindings + pure Python package
│   ├── core.cpp            # _core module bindings (about 1500 lines)
│   ├── include/            # binding-layer helper headers (core.h, BindUtils.h)
│   ├── pysparq/            # Python package: operators/ algorithms/ rir conformance dynamic_operator
│   └── test/               # pytest suite (incl. API contract tests for external consumers)
├── Experiments/            # quantum-algorithm C++ experiments (QDA/Grover/QFT/Shor/QCNN/CKS/GHZ etc.)
├── examples/               # C++ and Python examples (SPARQ_BUILD_EXAMPLES gates the C++ part)
├── test/                   # C++ tests (gated by SPARQ_BUILD_TESTS)
├── extern/qram-simulator/  # QRAM base submodule (Common + QRAM + ThirdParty; do not modify directly)
├── docs/                   # Sphinx docs + Doxygen (C++ API) + algorithm porting guide
└── pyproject.toml          # pysparq package (scikit-build-core + setuptools-scm)

SparQ/ - Sparse-State Simulator Core

Responsibilities: implements the core functionality of sparse-state quantum simulation (register management, gates, measurement, QRAM, quantum arithmetic).

Core classes (all under the qram_simulator namespace, declared in SparQ/include/basic_components.h):

  • System: a single computational basis state holding the complex amplitude and the register value array registers; it also maintains the global register table (names, types, widths) as static members, and is the hub of register-level programming

  • StateStorage: a quantum register storage cell

  • SparseState: a sparse quantum state holding std::vector<System>; default construction creates the |0...0⟩ initial state

  • BaseOperator: the unified operator interface (operator() / dag(), with CPU/GPU overloads), supporting composite and conditional operators

  • SelfAdjointOperator: base class of self-adjoint operators (dag() == operator()), e.g. Hadamard, Pauli-X

Main header modules:

Header

Contents

basic_components.h

core data structures such as System / SparseState / BaseOperator

basic_gates.h

standard gates such as Phase / Rotation / Pauli / S / T / RX-RI-RZ / SX / U2 / U3

hadamard.h

Hadamard on integer registers (superposition generation)

qft.h

QFT / InverseQFT / QFT_Full

measurement.h

mid-circuit measurement MeasureZ / Reset / Probability (Python page: measurement operators)

partial_trace.h

partial trace and readout

qram.h

QRAMLoad / QRAMLoadFast / QRAMInputGenerator

quantum_arithmetic.h

about 50 quantum arithmetic operators for modular add/sub/mul/div, shifts, comparisons, etc.

system_operations.h

AddRegister / RemoveRegister / Split / Combine / Push / Pop etc.

condrot.h / rot.h

conditional rotation, general unitary rotation, and state preparation

debugger.h

debug operators such as CheckNormalization / CheckNan / StatePrint

SparQ_Algorithm/ - High-Level Algorithm Library

Composes core primitives into complete quantum algorithms; each algorithm corresponds to a C++ experiment in Experiments/ and a Python implementation in PySparQ/pysparq/algorithms/ (see the algorithm porting guide for the mapping):

  • grover.h: QRAM-oracle-driven Grover search (incl. amplitude amplification and quantum counting)

  • shor.h: Shor factoring (standard + semiclassical variants)

  • state_preparation.h: QRAM-based state preparation

  • BlockEncoding/: tridiagonal-matrix block encoding and QRAM-based block encoding

  • DiscreteAdiabatic/: discrete adiabatic (QDA) linear-system solver

  • hamiltonian_simulation.h: Hamiltonian simulation via quantum walk / LCU / sparse-matrix oracle / QSVT

  • qcnn.h: quantum convolutional network (currently disabled as a whole by #if false)

PySparQ/ - Python Bindings and Pure-Python Layer

Exposes the core C++ API through pybind11 (PySparQ/core.cpp → compiled into pysparq._core), organized by the pure-Python package pysparq:

  • pysparq/operators/: operator base classes and the conditional-control mixin (conditional operations)

  • pysparq/algorithms/: pure-Python algorithm layer (Grover, Shor, QDA, CKS, state preparation, block encoding) — used in the Examples

  • pysparq/rir.py: the RIR interpreter (the QECC.Lang intermediate representation)

  • pysparq/dynamic_operator/: runtime JIT-compiled C++ dynamic operators (with a standalone loader)

  • pysparq/conformance.py: conformance-checking utilities

The thin qram_simulator binding does not live in this repository — it is packaged and released independently by the QRAM-Simulator core repository (pip install qram-simulator).

extern/qram-simulator/ - QRAM Base (submodule)

The QRAM circuit core (the qutrit/qubit implementations of QRAMCircuit, CuQRAMCircuit) and the Common infrastructure (math utilities, matrix wrappers, random-number engines, error handling). This directory belongs to another repository; do not modify it directly inside this repository; the upgrade path is git submodule update --remote followed by committing the new pin.

Quantum State Representation

┌──────────────────────────────────────────────────────────────┐
│                      SparseState                              │
├──────────────────────────────────────────────────────────────┤
│  Sparse storage: std::vector<System> basis_states            │
│  - Each System = { amplitude: complex, registers: uint64_t[] }│
│  - Register-value combinations are unique (amplitudes are summed and deduplicated on interference) │
│  - Only non-zero basis states with |amplitude| > ε are stored │
│  - Default construction creates the |0...0⟩ initial state    │
├──────────────────────────────────────────────────────────────┤
│  System (statically shared metadata)                         │
│  - name_register_map: [(name, type, size, status), ...]      │
│  - Registers are stored as uint64_t, supporting |a⟩|b⟩|c⟩ multi-register encoding │
└──────────────────────────────────────────────────────────────┘

Key properties:

  • Memory usage: O(k × r), where k is the number of non-zero basis states and r the number of registers

  • Compared with the O(2^n) of a dense representation, this enables much larger simulations

  • Register-level operations: AddRegister ≈ ⊗|0⟩, RemoveRegister ≈ PartialTrace

Key Design Decisions

Why Sparse-State Simulation

  1. Memory efficiency: the memory usage of the sparse representation is proportional to the amount of entanglement

  2. Computational efficiency: gate operations only need to touch basis states with non-zero amplitudes

  3. Where it shines: QRAM operations, quantum walks, sparse-Hamiltonian simulation

Qutrit-based vs Qubit-based QRAM

The core difference between the two lies in how the address is encoded, which in turn leads to different error scaling:

  • Qutrit-based (0/1/wait three-state encoding): the address has an off (wait) state

    • Classical information is encoded via classical controlled X

    • The Z basis is passed straight down, with no basis change

    • Error scaling: ε ∈ O(L²), where L is the layer number

  • Qubit-based (0/1 two-state encoding): the address has no off state and is always on by default (routing to the left)

    • The data qubit cannot be passed down directly; data must be converted to the Pauli-X basis

    • Classical information is injected via classical controlled Z

    • Error scaling: ε ∈ O(L³), where L is the layer number

Extensibility

Adding a New Quantum Gate / Operator

  1. Create a header file in SparQ/include/, deriving from BaseOperator (general operators) or SelfAdjointOperator (self-adjoint operators), and implement operator() and (if not self-adjoint) dag()

  2. Implement it in a same-named .cpp under SparQ/src/; the ClassControllable macro can be used to gain conditional-control capability

  3. To expose it to Python, add the binding in PySparQ/core.cpp (see the binding layer) and keep the _core.pyi type hints in sync

Adding a New Algorithm

  1. Create the algorithm header in SparQ_Algorithm/include/, composing core operators

  2. (Optional) Add a C++ experiment entry in Experiments/, a Python implementation under PySparQ/pysparq/algorithms/, and register the mapping in docs/algorithm-implementation.md

Build Options

  • SPARQ_BUILD_TESTS / SPARQ_BUILD_EXPERIMENTS / SPARQ_BUILD_EXAMPLES: CMake gates, OFF by default

  • CUDA/GPU backend: the code is kept in SparQ/include/cuda/ and SparQ/src/cuda/ (see the CUDA backend reference); CMake currently masks the GPU build