📊 Tracking Issue: Structured Quantum Programs

[burgholzer]

This issue tracks the effort to extend MQT Bench with support for structured quantum programs.

By structured quantum programs we mean hybrid quantum–classical programs that go beyond straight-line circuits and include:

• Structured control flow operations (if, for, while, etc.)
• Dynamic quantum circuit primitives (mid-circuit measurements, resets, classically controlled quantum gates)

The goal of this roadmap is to provide an overview of the different available kinds of structured programs and to act as a tracking hub for adding them to the MQT Bench suite.

👉 Contributions are highly encouraged! Even adding a single primitive or algorithm is already a great start. Please see our contribution guidelines before getting started.
👉 Important: Checkboxes should only be marked once the corresponding PR has been merged.

These benchmarks are expected to serve not only as functional tests but also as challenges for compilers, visualization engines, runtimes, and emulators, since they combine quantum and classical control in nontrivial ways.

---

🔁 Loops and Iteration

Loops are a fundamental control-flow construct. They can appear with static bounds (fixed iteration counts) or dynamic bounds (e.g., repeat-until-success). Many important algorithms can be expressed naturally in this form.

• Static loops

  • Example: Grover’s Algorithm (repeated oracle + diffusion steps)
    Ref: Grover, 1996
  • Example: GHZ state preparation (iterative entangling gates)
  • Example: Quantum Fourier Transform (QFT) (nested controlled rotations)
  • Example: Iterative Phase Estimation (iQPE) (looped controlled unitaries)
    Ref: Iterative QPE
  • Example: X-ray Absorption Spectroscopy (XAS)
    Ref: Quantum simulation of XAS and https://pennylane.ai/qml/demos/tutorial_xas

• Dynamic loops (Repeat-Until-Success)

  • Example: Quantum Metropolis Sampling
    Ref: Temme et al., 2011
  • Example: ML-QAE (Quantum Amplitude Estimation)
    Ref: Suzuki et al., 2020

---

🧱 Block Encoding

Block encoding embeds classical data or operators into quantum states. It underpins advanced algorithms like QSVT.

• Block encoding primitive
  Ref: Quantum Singular Value Transformation (QSVT)
  • Example: QSVT / QSP
    Ref: Low & Chuang, 2016

---

✨ Teleportation

Quantum teleportation is a canonical primitive for quantum communication and distributed computing.

• Teleportation primitive
  Ref: Bennett et al., 1993
  • Example: Teleportation-based subroutines (used in distributed algorithms, fault-tolerant protocols)

---

🎛 Multiplexers

Quantum multiplexers allow conditional application of gates and are widely used in circuit synthesis and algorithm design.

• Multiplexer primitive
  Ref: Quantum multiplexers in circuit synthesis
  • Example: Grover’s Algorithm (oracle construction often uses multiplexed operations)

---

🔄 Dynamic Qubit (Re)-Allocation

Dynamic allocation and reuse of qubits is crucial for resource-efficient algorithms. This often involves mid-circuit measurement and reset.

• Dynamic qubit allocation primitive
  • Example: Iterative Phase Estimation (iQPE)
  • Example: Iterative QFT
  • Example: Shor’s Algorithm
    Ref: Shor, 1994

---

⚛️ Loosely Coupled Hybrid Programs

Variational and hybrid algorithms naturally combine quantum circuits with classical optimization loops. They are loosely coupled because the quantum and classical parts interact only at well-defined synchronization points.

• VQE (Variational Quantum Eigensolver)
  Ref: Peruzzo et al., 2014

• QAOA (Quantum Approximate Optimization Algorithm)
  Ref: Farhi et al., 2014

---

🧩 Fault-Tolerance & Resource States

Structured programs also include primitives for error correction and fault-tolerant computation.

• Magic State Distillation
  Ref: Bravyi & Kitaev, 2005

[josh146]

Nice!

A couple of quick flyby comments:

• I could be wrong, but does IQPE not have dynamic loop bounds? I am trying to interpret the source code for the PL implementation

• X-ray Absorption Spectroscopy (XAS) I believe has static loop bounds, not dynamic. The structure of the circuit can be seen here

[burgholzer]

Nice!

A couple of quick flyby comments:

• I could be wrong, but does IQPE not have dynamic loop bounds? I am trying to interpret the source code for the PL implementation
• X-ray Absorption Spectroscopy (XAS) I believe has static loop bounds, not dynamic. The structure of the circuit can be seen here

Thanks for chiming in!

• Updated the description for XAS and added the link to the Pennylane implementation
• For a given, fixed precision p, which is an input to the program, there will always be p iterations of the loop. This can be seen fairly nicely in the OpenQASM 3 Paper (https://arxiv.org/abs/2104.14722; specifically Section 6, page 42). I'll paste this circuit into the comment here:

/*
 * Iterative phase estimation
 */
OPENQASM 3;
include "stdgates.inc";

const n = 3; // number of iterations
const θ= 3 * π / 8; // phase angle on target qubit

qubit q; // phase estimation qubit
qubit r; // target qubit for the controlled-unitary gate
angle[n] c = 0; // phase estimation bits

// initialize
reset q;
reset r;

// prepare uniform superposition of eigenvectors of phase
h r;

// iterative phase estimation loop
for k in [1:n] { // implicitly cast val to int
  reset q;
  h q;
  ctrl @ pow(2**k) @ phase(θ) q, r;
  inv @ phase(c) q;
  h q;
  measure q -> c[0];
  // newest measurement outcome is associated to a π/2 phase shift
  // in the next iteration, so shift all bits of c left
  c <<= 1;
}

// Now c contains the n-bit estimate of ϕ in the
// eigenvalue e^{i*ϕ} and qreg r is projected to an
// approximate eigenstate of the phase gate.

[glassnotes]

I have PennyLane or PennyLane + Catalyst implementations of the following:

• Teleportation
• Grover
• Shor's algorithm (which includes an implementation of measure-and-reset QFT/QPE that can be extracted)
• ML-QAE

Some are examples from my course (ML-QAE in particular, I am using as an assignment in a few weeks, so I will send that through a separate channel).

Unfortunately I can't do a lot of programming myself right now, but I can provide guidance on how to adapt the existing code.