ESSENCE and CARVE

Extended Stabilizer Simulation for Nonstabilizer Circuit Expectation and Circuit-Adaptive Reduction via Variation Estimation.

This repository contains the official implementation of the algorithm, test cases, and test case generators presented in the paper: "Efficient expectation value estimation for quantum circuits via extended stabilizer frameworks and adaptive variance estimation".

Overview

Classical simulation of quantum circuits with non-Clifford operations is a severe computational bottleneck when benchmarking quantum hardware or exploring quantum advantage.

This repository implements ESSENCE (Extended Stabilizer Simulation for Estimating Nonstabilizer Circuit Expectation), an efficient framework that integrates the sum-over-Clifford (SoC) method with extended stabilizer simulation to directly estimate expectation values. To overcome the extreme sampling overhead dictated by worst-case Hoeffding bounds, ESSENCE is combined with the CARVE (Circuit-Adaptive Reduction via Variation Estimation) protocol. CARVE employs adaptive online variance estimation to dynamically terminate simulations exactly when a predefined error bound and confidence are met.

Key Theoretical Advantages

• Space Complexity: $\mathcal{O}(n^2)$ memory efficiency, avoiding massive channel-decomposition search sizes.
• Time Complexity: Achieves an $\mathcal{O}(\xi_\star \epsilon^{-1} \log(\delta^{-1}))$ scaling in low-variance circuits, effectively reducing the dependence on the gate-wise stabilizer extent ($\xi_\star$) from quadratic to linear.

Repository Structure

The repository is organized into four main directories:

1. /algorithm (The Algorithm Itself)

Contains the core framework implementation, including:

• ESSENCE Simulator: Efficient tracking and sampling of stabilizer branches within the SoC representation.
• CH-Form Operations: Implementation of C-type matrix products and inner products of stabilizer states using efficient bitwise operations.
• CARVE Protocol: Adaptive variance estimation using Welford's online algorithm to dynamically halt the simulation.

2. /testcases (Paper Benchmarks)

Contains the exact test circuits and datasets used to benchmark the algorithm in the paper. The default parameters for these tests were evaluated at confidence bounds $\epsilon = 0.2$ and $\delta = 0.2$.

• QAOA Ansatz (MaxE3LIN2): Pre-generated circuits for MaxE3LIN2 problem instances (e.g., N20D3, N60D4) with fixed $\beta=\pi/4$.
• Quantum Kernel Estimation (QSVM): Pre-generated Pauli feature map circuits with $Z$ and $ZZ$ rotations for $n=2, 5$, and $64$ qubits, evaluated over uniformly generated random data vectors.

3. /generator (Testcase Generator)

Contains the Python scripts utilized to procedurally generate the benchmarks.

• Use these scripts to generate custom QAOA problem instances with varying degrees and qubit counts.
• Generate custom Quantum Kernel Estimation feature states and random classical data vectors.

4. /data (Simulation results)

Contains the per-circuit detail CSVs generated by ESSENCE/CARVE runs, named details_<testcase_name>_<timestamp>.csv. These files record circuit metadata, estimator settings, adaptive variance statistics, estimated results, and timing information.

Running the Benchmarks

For detailed testcase and generator guidlines, see GUIDELINES.md.

Build

cd algorithm
make

This creates:

algorithm/code

Run

Run:

cd algorithm
./code

For the default estimator settings, answer y, then enter the testcase name:

Default setting? (y/n): y
test file name: QKE_n2

The simulator writes a per-circuit detail CSV:

data/details_<testcase_name>_<timestamp>.csv

Generate A Random Pauli Feature-Map QKE Testcase

Build:

cd testcase_generator
make

This builds qke_gen and qaoa_gen.

Generate a 64-qubit QKE testcase with 10 random samples:

./qke_gen 10 64 5489 QKE_n64 full

This writes ../testcases/QKE_n64/. Then run:

cd ../algorithm
printf "y\nQKE_n64\n" | ./code

Pair modes:

full       N^2 pairs, including self-pairs and reverse pairs
ordered    N(N-1) pairs, excluding self-pairs
unordered  N(N-1)/2 pairs, excluding self-pairs and reverse duplicates

Generate An E3LIN2 Testcase

Build:

cd testcase_generator
make

Generate 60 qubits degree 4 ansatzs for 31 gamma values:

./qaoa_gen 60 4 31

This writes ../testcases/N60D4/.

Exact Ground Truth For Small Testcases

Use dense statevector simulation for small instances:

cd testcases
python3 statevector_ground_truth.py QKE_n5

This writes:

testcases/QKE_n5/ground_truth_statevector.csv

The default safety limit is 20 qubits.

Citation

If you use this code in your research, please cite the original paper:

Yunseo Hwang, Giwon Song, Kyoung Keun Park, Hyukjoon Kwon, and Taehyun Kim. Efficient expectation value estimation for quantum circuits via extended stabilizer frameworks and adaptive variance estimation.

License

This project is licensed under the Apache License 2.0 - see the LICENSE file for details.

Portions of the code are derived from Qiskit, which is also licensed under the Apache License 2.0. The Qiskit-derived files retain the original IBM copyright notice and include notices indicating our modifications.