PaperlayerView exact revision on arXiv

Source-linked AI summary

A Sparse and Truncated State Vector Simulator for Peaked Circuits

Diogo R. Ferreira

arXiv:2607.07816v1quant-phcs.ET

TL;DR

Peaked circuits require identifying their most probable output when exact state-vector simulation exceeds classical storage. The paper develops a sparse, truncated simulator with CPU/GPU vectorization and reports correct identification with fewer than 25 terms, while performance scales with the truncation size.

  • Problem

    The central problem is identifying the most probable output bit string when exact state-vector simulation exceeds available classical storage.

  • Method

    The approach uses sparse state vectors, top-k or probability-mass truncation, vectorized CPU/GPU operations, and gate reordering with fusion.

  • Results

    <25 terms found the correct output for the sharp-peak circuit; simulation time scaled linearly with k, while GPUs were about an order of magnitude faster at larger k.

  • Takeaways & Limitations

    The proposed simulator is a useful addition to circuit-simulation tools, complementing existing exact and approximate techniques.

  • Takeaways & Limitations

    A circuit that spreads probability mass across many basis states can undermine truncation, so concentrated mass is an essential assumption.

Abstract

from arXiv · show

In a class of quantum circuits known as peaked circuits, the goal is to predict the most probable bit string at the output of the circuit. Since these circuits are designed to have a sharp peak in their output distribution, in principle it should be possible to simulate them using a truncated state vector with a limited number of terms, or a fraction of the total probability mass. This approximate simulation can be carried out on a classical computer with a sparse representation that stores only the nonzero amplitudes of the state vector, in contrast to the dense representations that are common in most quantum simulators. For efficiency, all operations on the state vector should be vectorized to the furthest possible extent and, if available, hardware acceleration can also be used. This work describes how these requirements were met in an open-source implementation, and discusses its performance and limitations.

I. INTRODUCTION

State-vector terms can grow exponentially during circuit evolution, making exact classical simulation infeasible once memory limits are reached. The paper proposes a sparse, truncated approach to identify the most probable output bit string in peaked circuits.

  • State-vector growth: Although circuits often begin with one nonzero ground-state term, operations can cause the number of terms to grow exponentially.Superposition may double terms, entanglement may quadruple them, and three- or four-qubit operations could multiply them by 8 or 16.
  • Truncation: When memory limits make exact simulation infeasible, approximate simulation can retain only the most significant state-vector terms.Truncation may use a hard storage limit or a threshold requiring a minimum fraction of probability mass to remain.
  • Proposed approach: The proposed sparse and truncated simulator targets the most probable output bit string of peaked circuits, whose distributions favor a specific bit string.Peaked circuits combine random-looking layers with peaking layers that selectively boost a target string’s amplitude.

II. SPARSE STATE VECTORS

Sparse state-vector simulators store only nonzero amplitudes, avoiding the O(2n) memory footprint of dense arrays when states remain sparse. However, exact sparse simulation retains every nonzero amplitude and can lose its advantage as states become mostly dense.

  • Dense state-vector simulation: Dense simulators store 2n complex amplitudes and apply gate-specific linear transformations to array slices or strides.This representation maximizes locality and processor utilization but requires O(2n) memory.
  • Sparse simulator implementations: qblaze combines a cache-friendly sparse representation with multi-core algorithms that scale across CPUs.It reports significant speedups over prior sparse tools and mainstream dense simulators.
  • Limitations: Exact sparse simulators track all nonzero amplitudes, benefiting from sparsity and multi-core CPUs but generally underperforming dense simulators on mostly dense states.Their advantage depends on the state vector remaining sparse.

III. TRUNCATED STATE VECTORS

This section presents truncated state-vector simulation as a resource-bounded approximation that retains relevant basis states while trading fidelity for memory and runtime savings. It introduces top-k and p-mass truncation to control either the number of terms or retained probability mass, with renormalization after truncation.

  • Resource-bounded approximation: Truncation keeps a manageable number of nonzero amplitudes that fits a classical computer’s memory and processing limits.The approach abandons exact simulation in exchange for a resource-bounded state vector.
  • Resource-bounded approximation: Retaining relevant basis states and discarding a controlled tail enables a fidelity–memory–runtime trade-off, especially for highly entangled circuits.The retained state is renormalized after the discarded tail is removed.
  • Motivation: The method targets peaked distributions and other settings where observables are dominated by a small subset of basis states.Such truncation can provide orders-of-magnitude savings while maintaining accuracy within experimental or algorithmic tolerances.
  • Truncation methods: The proposed methods are top-k truncation, which imposes a maximum number of nonzero amplitudes, and p-mass truncation, which imposes a minimum retained probability mass.Both retain the largest-magnitude amplitudes; when both controls are specified, p-mass truncation is applied first and top-k truncation last if needed, followed by renormalization.
  • Truncation methods: Top-k directly controls runtime and memory, whereas p-mass more naturally controls observable fidelity, allowing resource or accuracy budgeting.The unused method can serve as a secondary knob for navigating the efficiency–fidelity trade-off.

IV. VECTORIZED OPERATIONS

The simulator relies on vectorized bulk array operations because it repeatedly updates many amplitudes, basis indices, and array elements, enabling numerical libraries to exploit modern hardware efficiently.

  • Vectorized operations: Vectorized operations let numerical libraries exploit cache locality, special processor instructions, and multi-threaded routines when applying repeated algebraic updates.These updates target many amplitudes, basis indices, and array elements.
  • Vectorized operations: Bulk array transformations improve the efficiency of repeated state-vector evolution and truncation, even when the retained amplitude array contains millions of elements.The implementation is designed to leverage modern CPU and GPU architectures despite retaining far fewer terms than 2^n.

A. State-Vector Evolution

State-vector evolution applies an m-qubit unitary to groups of 2^m amplitudes sharing the same remaining-bit pattern. The implementation derives new basis states with vectorized bitwise operations and resolves overlapping contributions through segmented sums, a common performance bottleneck.

  • Unitary application: An m-qubit unitary updates every tuple of 2^m amplitudes whose basis states differ only on those m qubits.The unitary has dimensions 2^m × 2^m, with each column multiplied by the corresponding amplitude.
  • Basis-state generation: New basis states are obtained from nonzero amplitudes through vectorized bitwise operations on their corresponding bit patterns.A new nonzero amplitude receives the basis state associated with its binary bit pattern.
  • Collision handling: Each new amplitude may combine 2^m contributions, requiring the implementation to collect and add contributions that map to the same basis state.Most gates operate on one, two, or three qubits, so m is typically small.
  • Collision handling: Segmented sums group contributions by basis state and sum within each group, but this step is often the main performance bottleneck during state evolution.Modern CPU and GPU libraries support segmented sums despite their challenges on parallel hardware.

B. State-Vector Truncation

State-vector truncation supports top-k and p-mass limits, with parallelizable array operations but sorting as the main bottleneck before selection and renormalization.

  • State-Vector Truncation: Top-k or p-mass truncation parallelizes array operations, but sorting amplitudes by decreasing squared magnitude is the main bottleneck.After sorting, terms are selected by the specified k limit or cumulative probability p threshold.
  • State-Vector Truncation: The truncated state vector is renormalized after retaining terms according to the k limit or p threshold.For p-mass truncation, terms are kept until their cumulative probability satisfies the desired threshold.

V. HARDWARE ACCELERATION

The simulator adds a GPU backend by substituting GPU equivalents for vectorized CPU operations with minimal code changes. Keeping state-vector data on the device yields preliminary speedups of about an order of magnitude, while GPU memory may be more constrained.

  • GPU backend design: The GPU backend replicates the CPU’s vectorized operations, requiring only minor code changes and avoiding handwritten kernels or architecture-specific tuning.Nearly identical CPU and GPU code simplifies maintenance.
  • Numerical precision: 128-bit complex amplitudes, 64-bit floating-point components, and 64-bit integer basis states are used by both backends.The integer representation theoretically limits simulations to 2^64 basis states and n≤64 qubits, though memory is exhausted sooner in practice.
  • Data movement: State-vector arrays remain on the GPU throughout simulation, with only final results transferred back to the host.Transferred results can include the most probable bit string.
  • Performance: About an order of magnitude speedup is indicated when switching from the CPU to the GPU backend, although GPU memory can be more constrained.These are preliminary benchmark results.

VI. APPLICATION TO PEAKED CIRCUITS

Peaked circuits concentrate probability on a few basis states, making sparse truncated-state simulation attractive. However, deep and highly entangling circuits can spread substantial probability across many states, causing uneven performance and motivating evaluation on challenging examples such as sharp peak.

  • Motivation: Peaked circuits concentrate amplitudes around one or a few dominant basis states, so sparse truncated-state simulation can represent the states contributing most probability mass.The remaining basis states contribute negligibly to the overall probability mass in this circuit class.
  • Theoretical basis: Runtime nO(log n) is sufficient for approximating output distributions of peaked shallow circuits, supporting the theoretical viability of sparse descriptions.This applies when each output qubit depends only on a constant-size neighborhood of input qubits.
  • Limitations: Deep or strongly entangling circuits may spread substantial probability across enormous numbers of basis states, requiring many more retained amplitudes to control truncation error.A peaked output distribution does not guarantee that state evolution can account fully for the distributed probability mass.
  • Limitations: Performance varies across peaked circuits: the method can identify the most probable output when probability stays concentrated, but can fail when a prominent peak coexists with broadly distributed mass.This uneven behavior motivates investigation across a variety of peaked circuits.
  • Evaluation examples: BlueQubit’s peaked-circuit hackathons provide examples for evaluation, including sharp peak, which uses arbitrary single-qubit rotations interleaved with controlled-Z gates.The circuit is designed as a challenging test case for the proposed approach.
  • Evaluation examples: 44 qubits and 580 instructions make sharp peak a large, deep, highly entangling ring circuit that challenges dense simulators and MPS methods.Its wrap-around coupling connects qubits 0 and 43, completing the ring connectivity.

A. Circuit Simulation Strategy

The simulation strategy combines sparsity-aware gate reordering with block-level gate fusion, then applies truncation after each fused-unitary update using either top-k or p-mass.

  • Circuit Simulation Strategy: Gate reordering keeps the active-qubit set small and postpones additional qubits when dependencies allow, limiting exponential growth while preserving circuit logic.Only commuting or dependency-compatible gates are reordered.
  • Circuit Simulation Strategy: Block-level gate fusion combines single- and two-qubit gates into multi-qubit unitaries, reducing state-vector updates from one per gate to one per block.Fusion also makes truncation less aggressive by applying it once at the block level.
  • Circuit Simulation Strategy: Simulation iterates over reordered blocks, updates the sparse state vector with each fused unitary, and truncates afterward using top-k or p-mass.The workflow first identifies the blocks before processing them sequentially.

B. Performance Scaling

Performance scales predictably under top-k truncation but differs by backend, with GPU acceleration becoming advantageous at larger k. State-vector size can grow exponentially under instruction blocks or high p-mass fractions, yet peaked circuits may still reveal the most probable bit string using far fewer than 2^n terms.

  • Term requirements: Fewer than 25 terms suffice to find the correct output bit string for the sharp peak circuit, although other circuits may require substantially more.The required term count depends on the circuit and motivates analyzing scaling as the state vector grows.
  • Top-k truncation: Simulation time increases linearly with k across multiple orders of magnitude under top-k truncation.The CPU version most clearly exhibits proportionality to k.
  • Top-k truncation: At larger k, the GPU version is about an order of magnitude faster, after fixed overhead dominates its low-k performance, until device memory is exhausted.The fixed GPU overhead is apparent at low k, while the larger-k advantage persists up to the device-memory limit.
  • Top-k truncation: Under top-k truncation, instruction blocks can double the number of terms, producing staircase-shaped exponential growth until the limit k.Other blocks initially leave the state-vector size unchanged, and larger term counts increase the time needed to process each instruction block.
  • p-mass truncation: A p-mass fraction of 99.9% allows the state vector to grow past 228 terms, whereas lower fractions keep the number of terms smaller.Unlike top-k truncation, p-mass truncation truncates after each circuit block, but high retained probability mass can exceed anticipated limits.
  • p-mass truncation: As retained probability mass approaches 100%, the observed term count grows rapidly toward 2^n, while peaked circuits may still be identified with well below 2^n terms.Here, n denotes the number of qubits; the steepness of the growth region suggests high probability mass can coexist with substantially fewer terms.

VII. CONCLUSION

The work presents a sparse, truncated state-vector simulator with efficient CPU/GPU vectorization and gate reordering and fusion for peaked circuits. It is effective when probability mass remains concentrated, but can fail when circuits spread it broadly; future preprocessing may improve performance.

  • Contributions: The simulator combines sparse, truncated state-vector representation, efficient vectorized CPU and GPU operations, and gate reordering and fusion to delay state-vector growth.The circuit strategy is designed specifically for peaked circuits.
  • Truncation methods: Two truncation methods contain growth by limiting the number of terms or retaining a fraction of total probability mass.Both methods prioritize the largest-amplitude components.
  • Truncation methods: The truncation approach assumes that probability mass remains concentrated on a few basis states so the largest-amplitude components identify the most probable output.This assumption supports the method’s application to peaked circuits.
  • Limitations: Circuits that spread probability mass across very many basis states can undermine any truncation method, although the approach works for the studied peaked circuit and a few others.The authors nevertheless describe it as a useful complement to exact and approximate circuit simulators.
  • Future work: Future integration of ZX-based optimization and other graph-based preprocessing methods may further enhance the simulator’s effectiveness on more difficult peaked circuits.These optimizations act before the actual simulation.
Loading 2607.07816v1…