QSeqSim: A Symbolic Simulator for Qiskit While Loops Using Sequential Quantum Circuits

This paper introduces QSeqSim, a Qiskit-integrated symbolic simulator that enables the efficient simulation of quantum programs with while-loops by translating them into sequential circuits and utilizing BDD-based weighted model counting to compute measurement probabilities for large-scale, multi-iteration benchmarks.

The Gist

Imagine you have a very sophisticated recipe for a quantum dish (a quantum program). Most modern recipe books, like Qiskit, allow you to write instructions that say, "Keep cooking this step over and over again until the sauce turns a specific color." This is called a while loop.

However, until now, the kitchen appliances (simulators) that actually cook these recipes couldn't understand that instruction. If you tried to run a recipe with a "keep cooking until..." instruction, the appliance would just crash or say, "I don't know how to do this."

QSeqSim is a new, smart kitchen assistant designed specifically to handle these "keep cooking until" instructions. Here is how it works, using simple analogies:

1. The Problem: The "Loop" Gap

Think of a standard quantum circuit as a straight line of dominoes falling one after another. You push the first one, and they all fall in a fixed order. This is easy to simulate.

But a while loop is like a sliding door in a hallway. You walk through the door, do a task, check a sensor, and if the sensor says "not done yet," you slide back through the door to do it again. The state of the room (the quantum state) changes every time you go through, and the door might close at any moment.

Current tools (like Qiskit-Aer) can only handle the straight line of dominoes. They don't know how to handle the sliding door that loops back on itself. QSeqSim is the first tool built to understand and simulate this "sliding door" behavior natively.

2. The Solution: Turning Loops into a "Memory Machine"

To make sense of these loops, QSeqSim translates the quantum program into a special kind of machine called a Sequential Quantum Circuit.

• The Analogy: Imagine a factory assembly line.
  • External Qubits: These are like raw materials brought in fresh for every single pass through the loop. They are measured (checked) and then thrown away.
  • Internal Qubits: These are like the work-in-progress on the conveyor belt. They stay in the machine, get updated, and are carried over to the next loop iteration.
  • The Loop: The machine checks a gauge (a measurement). If the gauge says "keep going," the conveyor belt loops back, carrying the updated work-in-progress to the start of the next cycle.

QSeqSim treats the loop not as a magical repeat button, but as a physical machine with a feedback wire that carries the "memory" of the previous step into the next one.

3. The Engine: The "Smart Filing System" (BDDs)

Simulating quantum computers is hard because the number of possibilities grows explosively (like trying to track every possible path a traveler could take in a giant maze).

QSeqSim uses a technique called Binary Decision Diagrams (BDDs).

• The Analogy: Imagine you have a massive library of every possible outcome of your quantum loop. A normal computer tries to read every single book in the library one by one.
• QSeqSim's Trick: Instead of reading every book, QSeqSim uses a smart filing system. It notices that many paths in the maze are identical. It groups them together into a single folder.
  • If 1,000 paths all lead to the same result, QSeqSim doesn't calculate them 1,000 times; it calculates them once and says, "This folder represents all 1,000 paths."
  • This allows it to handle loops with over 1,000 qubits and more than 10 iterations without getting overwhelmed, something previous tools couldn't do.

4. What It Can Do (The Results)

The authors tested QSeqSim on three types of "recipes" (benchmarks) to see how well it handles the "sliding door" loops:

• Repeat-Until-Success (RUS): A recipe that says, "Keep trying this trick until it works." QSeqSim simulated this perfectly, even when the loop had to run 100 times.
• Quantum Random Walks: Imagine a drunk person walking on a grid, flipping a coin at every step to decide which way to go, and checking if they hit a wall. QSeqSim simulated a walk with over 1,000 steps (qubits) and 10+ loops.
• Grover's Search: A famous search algorithm that uses loops to find a needle in a haystack. QSeqSim could simulate this with hundreds of qubits.

5. Why This Matters (For Now)

The paper claims that QSeqSim fills a specific gap: it is the first tool that can actually run Qiskit programs containing while loops.

Before this, if a programmer wrote a loop, they had to manually unroll it (write out every single step) or couldn't run it at all. Now, they can write the loop naturally, and QSeqSim translates it into a "memory machine," uses its smart filing system to calculate the odds of different outcomes, and tells you exactly what happens.

In short: QSeqSim is a translator and a calculator that finally lets quantum computers understand and execute instructions that say, "Do this again and again until the result is right."

Technical Summary

Technical Summary: QSeqSim

Problem Statement

Despite the rapid evolution of quantum programming frameworks, a significant gap exists between the expressiveness of modern quantum languages and the capabilities of current execution backends. Specifically, while Qiskit and OpenQASM 3 support high-level control flow constructs such as while loops (enabling patterns like Repeat-Until-Success (RUS), weakly measured Grover search, and feedback-based quantum random walks), there is no Qiskit-native tool capable of simulating these programs.

The default simulator, Qiskit-Aer, and current cloud hardware backends do not support the while_loop construct. Attempts to execute such programs result in parsing or compilation errors because the control flow cannot be lowered to a circuit form that these simulators can process. Consequently, there is no execution engine that realizes the intended iterative semantics of non-trivial while-loop programs within the Qiskit ecosystem.

Methodology

The authors present QSeqSim, a symbolic simulation backend integrated with Qiskit that bridges this gap by interpreting while-loop programs as Sequential Quantum Circuits (SQCs). The methodology involves three core components:

1. Semantic Framework: From Combinational to Sequential

QSeqSim redefines the execution model for Qiskit programs containing classical control:

• Translation: It takes QuantumCircuit objects, translates them to OpenQASM 3, and parses them into an Abstract Syntax Tree (AST).
• Decomposition: The parser classifies circuit blocks into three types:
  • CQC (Combinational Quantum Circuits): Straight-line gate segments.
  • DQC (Dynamic Quantum Circuits): Blocks with mid-circuit measurements and conditional branching (if/else, switch).
  • SQC (Sequential Quantum Circuits): Blocks representing while loops.
• State Partitioning: For SQCs, the system explicitly partitions qubits into internal qubits (state retained and fed back across iterations) and external qubits (iteration-scoped qubits that are measured and discarded). This provides a precise semantics for quantum state feedback.

2. Symbolic Execution Engine (BDD-Based)

The core of QSeqSim is a Binary Decision Diagram (BDD)-based engine that extends existing Boolean encodings of quantum circuits (specifically the work of Tsai et al.) to handle sequential behavior:

• Symbolic Operators: The engine introduces two dedicated operators to manage state evolution across loop iterations:
  • State Composition: Tensors the current internal state with a fresh external input state.
  • State Retention: Performs a partial trace to discard measured external qubits while preserving the updated internal state for the next iteration.
• Operational Semantics: The simulator executes the program using a small-step operational semantics, unfolding while loops by repeatedly executing the body until the loop guard (derived from classical bits) evaluates to false.

3. Efficient Probability Computation

A major challenge in symbolic simulation is computing measurement probabilities for large, structured decision diagrams without explicit enumeration.

• Weighted Model Counting (WMC): Instead of using hyper-function constructions, QSeqSim employs weighted model counting on structured and sparse BDDs. This allows the system to aggregate contributions of basis states in time proportional to the BDD size, efficiently handling the probability queries required for mid-circuit measurements and loop guards.

Key Contributions

The paper claims the following primary contributions:

1. First Qiskit Backend with Direct While-Loop Support: QSeqSim is the first tool to directly execute Qiskit programs containing while loops by lowering them to OpenQASM 3 and providing an executable small-step semantics.
2. Extension to Sequential Boolean Models: It extends BDD-based encodings from purely combinational circuits to general sequential circuits by introducing symbolic operators for state composition and retention, enabling the modeling of explicit state feedback.
3. Scalable Symbolic Simulation: By leveraging mature BDD backends and WMC techniques, QSeqSim achieves efficient simulation of while-loop induced sequential circuits, scaling beyond the capabilities of existing tools.

Experimental Results

The authors evaluated QSeqSim on a MacBook Air (M2, 16 GB) using three benchmark categories:

• Repeat-Until-Success (RUS): The system successfully simulated RUS circuits with varying unitaries. While short loops (10 iterations) completed in under a second, longer loops (100 iterations) showed runtimes ranging from ~1.5s to ~108s, demonstrating sensitivity to the specific unitary's impact on BDD structure.
• Quantum Random Walk (QRW): The tool scaled to circuits with over 1000 qubits (specifically $N=1024$ position sites) for more than 10 loop iterations. However, performance was limited by the gate count per iteration; for $N=1024$, only up to 13 iterations were feasible within a 30-minute timeout.
• Grover's Search: Similar scalability trends were observed. For 256 qubits, the system handled up to 5 iterations before timing out, indicating that while BDDs handle deep loops well, very large multi-qubit operators combined with repeated iteration remain computationally intensive.
• Random While-Loops: On 100-qubit random circuits, QSeqSim remained tractable, with median runtimes staying under one minute across various gate and measurement densities.

The tool also demonstrated utility in reachability analysis, computing exact probabilities for specific state configurations (e.g., a walker reaching a specific position) and measurement outcome patterns (e.g., loop termination probabilities) without sampling noise.

Significance and Claims

The paper positions QSeqSim as a necessary bridge between the high-level expressiveness of quantum programming languages and the limitations of current simulators. Its significance lies in:

• Enabling Formal Analysis: By providing a native execution engine for while loops, it allows for the formal verification and analysis of quantum programs with feedback and measurement-controlled iteration, which were previously inaccessible in the Qiskit ecosystem.
• Scalability via Symbolism: It demonstrates that symbolic simulation using BDDs and weighted model counting can effectively handle sequential quantum circuits with substantial qubit counts and loop depths, outperforming naive statevector simulation for these specific structured problems.
• Foundation for Future Work: The authors note that while the current implementation runs on commodity hardware, the architecture is designed to support future deployment on server-class machines with parallelism to handle even larger-scale simulations and formal verification tasks.