✨ Add expected noise-free outputs for circuits

[grageragarces]

Problem Statement

It would be really useful if MQT Bench circuits came with their expected noise-free results (an ideal state vector or output probability distribution) so that downstream users can validate a experiments against an expected truth.
For small circuits or things like GHZ and W it doesn't matter, but for the more involved algorithms expected results aren't obvious from the circuit alone. For instance, in Grover, without knowing how the generator constructs the oracle, there's no way to tell which state the circuit is meant to amplify, so there's nothing to test against.

Proposed Solution

If you have them add them in some format. Maybe json would be good?
grover_indep_5.qasm → grover_indep_5_reference.json

[burgholzer]

Thanks for the suggestion @grageragarces 🙏🏼
This is something that has come up before in discussions and that would generally be helpful.
For many of the benchmarks, it is moderately easy to write a function that verifies a distribution of measurement counts against the expected distribution, or verifies that the "right" solution has been chosen most often.
There are two things that make this tricky:

• most of the benchmarks in MQT Bench are scalable in the sense that they can be instantiated for arbitrarily many qubits. This rules any kind of solution out that describes the reference as a dense state vector.
• only some of the benchmarks have a sparse output distribution with a clear thing to look for. Some are equal superpositions of a bunch of states; some are almost random. It is fairly hard to find general "acceptance criteria".

Would you have any ideas in mind for how the expected output could be structured?

[grageragarces]

I think to calculate the basic metrics (total variation distance (TVD), success probability, Hellinger fidelity, ...) we can just build a pointwise evaluator P(x) that we only need to query on the finite set of bitstrings we measure. Since the measured distribution Q should be finite, we should be good even at scale.

For fidelity this works because terms with Q(x) = 0 vanish, so the sum collapses onto supp(Q):

F(P,Q) = (Σ_x √(P(x)·Q(x)))²  =  (Σ_{x ∈ supp(Q)} √(P(x)·Q(x)))²

And TVD comes out too as long as P is normalized:

TVD(P,Q) = ½ Σ_x |P(x) − Q(x)|
         = ½ [ Σ_{x∈O} |P(x) − Q(x)|  +  Σ_{x∉O} P(x) ]
         = ½ [ Σ_{x∈O} |P(x) − Q(x)|  +  (1 − Σ_{x∈O} P(x)) ]

The metrics sum over bit strings so we can avoid vectors.

The file would need to describe which kind of evaluator a circuit enables, so the descriptor stays poly even when the distribution is exponential:

• sparse: an explicit {bitstring: prob} table (Grover, BV, Deutsch-Jozsa)
• uniform: uniform over a predicate-defined support (e.g. hamming_weight == 1 for W), stored as {predicate, size} so P(x) = 1/size if the predicate holds else 0
• analytic: a named distribution family plus params with a documented closed-form, so anyone can evaluate P(x) directly (e.g. QPE's phase-estimate profile, or a QFT of a known input)
• objective: when a distribution is the wrong target, ship the semantic answer or cost function instead. For QAOA/VQE that's the cost Hamiltonian (e.g. QUBO) plus optimal value, and the metric becomes the approximation ratio computed straight from samples; for Grover/BV it's just the marked states or hidden string

A quick brainstorm with the clanker outputs something like this:

{
  "circuit": "grover_indep_5",
  "n_qubits": 5,
  "measured_qubits": [0,1,2,3,4],
  "bit_order": "qiskit-little-endian",
  "reference": {
    "kind": "sparse",
    "normalized": true,
    "entries": {"00101": 0.9605, ...}
  },
  "objective": {"type": "marked_states", "states": ["00101"]},
  "metrics": {
    "hellinger_fidelity": {"applicable": true},
    "tvd": {"applicable": true},
    "success_probability": {"applicable": true, "target": "objective.states", "ideal": 0.9605},
    "linear_xeb": {"applicable": false}
  }
}

[grageragarces]

For random circuits I'm not sure this is doable tho. You could have:

  "reference": {
    "kind": "simulate"

with up to 40 qubits (or whatever your simulation limits are), and have the rest fall under a none default. I think it would be better to have it for some and not for others than to not have it at all.

[burgholzer]

Sorry for only getting back to you now. Didn't quite get to it over the course of the week.
I generally like the suggestions!
Maybe one could take some inspiration from metriq-gym (https://github.com/unitaryfoundation/metriq-gym) and how they define their benchmark schemata.
As far as I understand, they do not include the expected output in the schema, but formalized the expected inputs already.

Would this generally be something you'd be interested in contributing to MQT Bench?
Because we'd surely appreciate the contribution.