Simple Quantum State Encodings for Hybrid Programming of Quantum Simulators

Thomas Gabor, Marian Lingsch Rosenfeld, Claudia Linnhoff-PopienICSA Companion 2022 · DOI · OpenReview

TL;DR

This paper explores using simple classical data structures like databases to encode quantum states for simulation, finding they can outperform sophisticated simulators like Qiskit for "semi-quantum" circuits. This suggests a path towards more efficient hybrid quantum-classical programming by leveraging classical strengths for near-classical computations.

What Problem Does This Paper Address?

Quantum algorithms are often tested and developed on quantum simulators running on classical hardware, as real quantum computers are still limited. While these simulators aim to mimic actual quantum computers, the authors argue that for circuits producing "sparse" or "near-classical" quantum states, current simulators might not be optimally efficient. They propose that by using simpler, classical data structures to represent these states, simulation performance could be significantly improved, especially for hybrid programming scenarios where classical computations are deeply intertwined with quantum ones.

Methods

The authors compare four approaches for encoding quantum states:

  • Array: Using a standard NumPy array to store states with non-zero amplitudes.
  • Database: Employing an SQLite database to store states with non-zero amplitudes.
  • Qiskit: Utilizing the built-in simulator provided by the Qiskit toolkit as a benchmark.
  • Mixed: A heuristic approach that dynamically chooses between the Database encoding and the Qiskit simulator based on the circuit's "quantumness" (specifically, the proportion of qubits affected by Hadamard gates).

They also introduce a "state drop" technique for the Database approach, where states with the smallest amplitudes are removed after each quantum operation to limit database size, at the cost of introducing errors.

Datasets

The paper does not use external datasets. Instead, it introduces and evaluates three custom quantum circuit benchmarks:

  • Generate Superposition: A simple circuit applying Hadamard gates to a varying number of qubits.
  • Addition: A circuit implementing binary addition, with Hadamard gates applied to input variables.
  • Grover's Search: A standard quantum search algorithm, where the oracle is implemented using the addition circuit.

These benchmarks are designed to test scenarios with varying degrees of "quantumness" and sparsity in the resulting quantum states.

Key Insights and Ideas

  • Classical Simplicity Wins for Sparsity: For quantum states that are not highly entangled or complex (i.e., "semi-quantum" or sparse states), simple classical data structures like databases can be surprisingly efficient, often outperforming dedicated quantum simulators.
  • Simulator Optimization Mismatch: State-of-the-art simulators like Qiskit are optimized for general quantum circuits, which may not be ideal for recognizing and efficiently handling near-classical states.
  • Hybrid Programming Potential: The ability to efficiently simulate near-classical states using classical methods opens doors for more seamless hybrid quantum-classical programming, where classical components can be more deeply integrated.
  • "State Drop" Trade-off: The "state drop" technique, while introducing errors, shows a potential trade-off between computation time and accuracy, suggesting avenues for further research in approximate quantum simulation.
  • Heuristic Switching is Viable: A simple heuristic to switch between classical and simulator-based encodings based on circuit properties can dynamically leverage the strengths of each approach.

Key Results

  • In the "Generate Superposition" benchmark, the Database simulator's runtime was primarily dependent on the number of "Nondet qubits" (those affected by Hadamard gates), while Qiskit's runtime depended on the total number of qubits. The Database simulator generally outperformed Qiskit for fewer "Nondet qubits."
  • The "Addition" benchmark showed similar trends, with the Database simulator performing better than Qiskit for most cases, especially as the number of qubits increased. The Mixed simulator consistently chose the Database approach.
  • For "Grover's Search," the Database simulator also outperformed Qiskit, particularly when the "Nondet qubits" were a significant portion of the total qubits.
  • The "state drop" technique showed that while it can reduce computation time, it often leads to significant errors, with only a small regime where a beneficial trade-off was observed.

Limitations and Future Work

  • Limited Scope of "State Drop": The authors acknowledge that the "state drop" technique, as implemented, has limited success and deteriorates quickly with increasing error. They suggest further investigation into more advanced heuristics for this technique.
  • Heuristic Refinement: The "Mixed" heuristic is simple and could be improved for more complex real-world scenarios.
  • Broader Simulator Integration: Future work should consider integrating more quantum simulators and exploring a wider range of classical data structures.
  • Arbitrary Error/Time Trade-off: The ultimate goal is an integrated simulator that can dynamically recognize circuits and offer tunable trade-offs between computational resources and acceptable error.
  • Complex Algorithm Decomposition: Investigating how complex algorithms can be split and simulated using a combination of various techniques is a promising direction.

Summary updated

Abstract

Especially sparse quantum states can be efficiently encoded with simple classical data structures. We show the admissibility of using a classical database to encode quantum states for a few practical examples and argue in favor of further optimizations for quantum simulation targeting simpler, only "semi-quantum" circuits.
BibTeX
@inproceedings{gabor2022simple,
  author = {Thomas Gabor and Marian Lingsch Rosenfeld and Claudia Linnhoff-Popien},
  title = {{Simple Quantum State Encodings for Hybrid Programming of Quantum Simulators}},
  booktitle = {ICSA Companion},
  year = {2022},
  doi = {10.48550/arxiv.2204.11042},
}
Figure