⚛️ quantum physics

Orkan: Cache-friendly simulation of quantum operations on hermitian operators

This paper introduces Orkan, a cache-efficient simulation library that leverages a tiled memory layout to store only the lower triangle of Hermitian operators, thereby reducing both memory usage and wall-clock time by approximately half compared to existing simulators like Qiskit Aer, QuEST, and Qulacs.

Original authors: Timo Ziegler

Published 2026-04-20

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Timo Ziegler

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to simulate a complex quantum computer on a regular laptop. To do this, you have to track the "state" of every qubit (quantum bit). In the quantum world, things are messy: they can be in multiple states at once, and they interact in ways that create a massive amount of data.

Traditionally, simulators treat this data like a giant, messy spreadsheet where they write down every single number, even the ones that are just mirror images of others. It's like writing down a list of prices for 100 items, but then writing down the same list again in reverse order just to be safe. You end up using twice as much memory and twice as much time to do the math, even though the second list is completely redundant.

This paper introduces Orkan, a new software tool that changes how we organize this data to make quantum simulations faster and lighter.

Here is the breakdown using simple analogies:

1. The Problem: The "Mirror Room" Mess

In quantum physics, the data we simulate (called a Hermitian operator) has a special property: it's perfectly symmetrical, like a reflection in a mirror. If you know the top half of the data, you automatically know the bottom half.

Old Way (The Cluttered Attic): Traditional simulators (like Qiskit Aer or QuEST) ignore this symmetry. They store the whole "room," including the mirror image. This is like storing a photo of a room and then taping a second, identical photo to the wall just to be sure. It wastes space and forces the computer to carry around heavy, unnecessary luggage.
The Consequence: As you add more qubits, the amount of data explodes. Eventually, the computer runs out of "RAM" (short-term memory), and it starts swapping data to the slow hard drive. This is called memory thrashing, and it makes the simulation crawl to a halt.

2. The Solution: The "Smart Tiling" System

The author, Timo Ziegler, created Orkan, which uses a Tiled Memory Layout.

The Analogy: Imagine you are organizing a library. Instead of putting every single book on a giant, continuous shelf (which is hard to navigate), you break the books into small, manageable boxes (tiles).
The Trick: Because the data is symmetrical, Orkan only stores the "lower triangle" of the data. It throws away the mirror image.
The "Tile" Magic: It cuts the data into small square chunks (tiles).
- Cache Friendly: These tiles are sized perfectly to fit into the computer's fastest memory (L1 cache), like keeping your most-used tools on your workbench rather than in the garage.
- No Branching: Old methods had to constantly ask, "Is this number on the top or bottom?" (a "branch" in code). Orkan knows exactly where everything is, so it doesn't waste time asking questions. It just grabs the tile and works.

3. The Result: Running a Marathon with a Backpack

The paper compares Orkan to the top competitors (Qiskit Aer, QuEST, Qulacs).

Memory Savings: By only storing the necessary half of the data, Orkan cuts the memory usage by roughly 50%.
Speed: Because the computer doesn't have to carry the extra "mirror" data, and because the data is organized in neat, fast-access tiles, the simulation runs 2 to 4 times faster.
The "Thrashing" Fix: At the limit of what a computer can handle (15 qubits), the old simulators run out of RAM and start swapping data to the slow hard drive. Orkan, being half the size, fits comfortably in the fast memory and keeps running at full speed. In the tests, Orkan was 14 times faster than the competition at this limit.

4. Why Does This Matter?

Think of quantum simulation as a "flight simulator" for quantum computers. Before we build the real, expensive quantum hardware, engineers need to test their software on classical computers.

Better Design: If the simulator is slow, engineers can't test complex algorithms. Orkan makes testing faster, allowing for better quantum software design.
Noise Testing: Real quantum computers are noisy (prone to errors). Orkan can simulate these errors more efficiently, helping scientists figure out how to fix them.
Universal: It works whether you are looking at the system from the "state" perspective (Schrödinger picture) or the "measurement" perspective (Heisenberg picture). It treats them all the same, simplifying the code.

Summary

Orkan is like upgrading from a moving truck that carries double the furniture you actually need, to a smart, compact van that only carries what's essential and organizes it perfectly for quick unloading. It doesn't just save space; it fundamentally changes the workflow to make quantum simulation significantly faster, allowing researchers to push the boundaries of what we can simulate on today's computers.

1. Problem Statement

Classical simulation of quantum computers is vital for algorithm design, noise characterization, and hardware benchmarking. While state-vector simulators are efficient for pure states, they cannot natively handle general quantum operations (completely positive maps) without resorting to stochastic ensembles or vectorizing the density matrix into a $2n$ -qubit state.

Key Challenges Identified:

Memory Inefficiency: Established simulators (e.g., Qiskit Aer, QuEST) typically vectorize the density matrix, storing all $N^2$ elements ( $N=2^n$ ) and ignoring the Hermitian symmetry ( $H = H^\dagger$ ), which theoretically allows storing only half the data.
Cache Misses & False Sharing: Traditional "packed" storage of the lower triangle of a Hermitian matrix leads to irregular memory access patterns, causing frequent cache misses and load imbalance in parallel environments.
Two-Pass Overhead: To simulate a gate on a vectorized density matrix, simulators often apply the operation in two passes (e.g., $U \rho U^\dagger$ ), effectively doubling memory traffic compared to a single-pass update.
Lack of Generality: Many simulators rely on structural assumptions (stabilizer, tensor networks) that break down for generic quantum operations or mid-circuit measurements.

2. Methodology: The Orkan Library

The paper introduces Orkan, a simulation library designed to evolve general Hermitian operators (representing either density matrices or observables) under completely positive maps.

A. Theoretical Foundation

Kraus Representation: The system evolves via $\Phi(H) = \sum_\alpha K_\alpha H K_\alpha^\dagger$ .
k-local Decomposition: For operations acting on $k$ qubits, the $N \times N$ matrix is decomposed into $2^{n-k}$ invariant subspaces. The update reduces to independent $2^k \times 2^k$ block updates.
Gather-Transform-Scatter: Instead of permuting the entire matrix, the algorithm reconstructs global indices on the fly using bitwise operations to gather specific $2^k \times 2^k$ blocks, applies a precomputed transfer matrix (Liouville representation), and scatters the result back.

B. The Tiled Memory Layout

The core innovation is a tiled memory layout that stores only the lower triangle of the Hermitian matrix at a tile granularity.

Structure: The matrix is divided into square tiles of size $M \times M$ (where $M=2^m$ ). Only tiles $T_{i,j}$ where $i \ge j$ are stored in a contiguous array.
Row-Major Within Tiles: Elements inside each tile are stored in row-major order to maximize SIMD (Single Instruction, Multiple Data) vectorization.
Diagonal Tiles: Diagonal tiles store all $M^2$ elements (not just the lower triangle) to eliminate per-element branching logic during updates.
Benefits:
- Memory Footprint: Reduces storage by roughly 50% compared to full vectorization, with negligible overhead (<0.1%) compared to a naive packed format for large $n$ .
- Cache Locality: Tiles fit comfortably within L1/L2 caches (e.g., 16 KiB for $M=32$ ), ensuring working sets remain resident.
- Parallelism: Assigning whole tiles as atomic work units to threads eliminates "false sharing" (threads writing to the same cache line) and ensures perfect load balancing.

C. Update Algorithms

The library implements two distinct update paths based on the qubit index relative to the tile size:

Intra-tile operations ( $a < m$ ): Updates occur entirely within a single tile. The working set stays in L1 cache, and the loop is embarrassingly parallel.
Cross-tile operations ( $a \ge m$ ): Updates span up to four tiles. The algorithm uses a three-way branch to handle tiles in the lower triangle, the upper triangle (accessed via the adjoint of the stored lower tile), and diagonal cases. This logic is optimized to minimize branching overhead.

D. Native Gate Optimization

For native gates (e.g., Pauli-X, SWAP, Toffoli), Orkan uses dedicated code paths that avoid arithmetic operations entirely.

Pauli-X: Reduces to memory swaps ( $h_{i,j} \leftrightarrow h_{i \oplus 2^a, j \oplus 2^a}$ ).
Phase Gates: Implemented via real-valued shuffles and negations.
Single-Pass Conjugation: Unlike vectorized approaches that require two passes ( $U \rho U^\dagger$ ), Orkan updates the Hermitian matrix in a single pass, halving memory traffic for these operations.

3. Key Contributions

Hermitian-Aware Storage: A novel tiled format that exploits Hermitian symmetry without the performance penalties of packed storage (branching, cache misses).
Unified Picture: The implementation is agnostic to the Schrödinger (state evolution) or Heisenberg (observable evolution) picture, treating both as updates to a Hermitian operator.
Dedicated Kernels: Algorithms that combine gather-transform-scatter kernels for generic operations with specialized, zero-arithmetic paths for native gates.
Open Source Library: Release of the Orkan library with benchmarking scripts.

4. Results and Benchmarks

The author benchmarked Orkan against Qiskit Aer, QuEST, and Qulacs on an Apple M3 Pro (16 GB RAM) for up to 15 qubits.

Generic Operations (Depolarising Channel):
- Speedup: Orkan (tiled) achieved 2–4× wall-clock speedups over competitors in the intermediate regime ( $10 \le n \le 14$ ).
- Large Systems ( $n=15$ ): Competitors suffered a massive slowdown (14× slower) due to memory thrashing (working set > physical RAM). Orkan maintained throughput because its reduced memory footprint (~8 GB) kept the data in RAM.
- Bandwidth: Orkan achieved effective bandwidths of ~120 GiB/s, approaching the hardware limit, while competitors were limited by redundant memory traffic.
Native Gates (Pauli-X):
- Speedup: Orkan achieved up to 4× speedup for intermediate systems and 22× for $n=15$ compared to the best competitor (QuEST).
- Cause: The speedup is attributed to the combination of reduced memory footprint and the elimination of the two-pass overhead inherent in vectorized simulators.
Small Systems ( $n \le 7$ ): Packed format slightly outperformed tiled due to padding overhead, but tiled quickly surpassed it as matrix size exceeded L1/L2 cache capacity.

5. Significance

Scalability: By halving the memory footprint, Orkan allows the simulation of larger quantum systems (e.g., $n=16$ ) on standard hardware where full-vectorization simulators would fail due to out-of-core swapping.
Efficiency: The work demonstrates that exploiting Hermitian symmetry via cache-friendly tiling is not just a memory optimization but a critical performance enabler for high-fidelity quantum simulation.
General Applicability: The method supports arbitrary completely positive maps, making it ideal for simulating realistic noise, mid-circuit measurements, and error correction codes where structural assumptions (like low entanglement) do not hold.
Future Impact: The tiled structure provides a natural foundation for future distributed and GPU-accelerated implementations, bridging the gap between quantum simulation and High-Performance Computing (HPC) best practices.