Case Study: Bernstein-Vazirani as a System Benchmark

Executive Summary

Bernstein–Vazirani is a modest algorithm — $n$ queries down to one — and one of the most-run circuits in the industry. The reason is not its speedup. It is that on a perfect device the algorithm returns one specific bitstring with probability 1, so every deviation from that bitstring is hardware error, requiring no statistical modelling to interpret.

This case study uses BV as an instrument: run it at increasing widths, watch success probability decay, fit the decay to a per-gate error model, and extract a system-level error rate that predicts other circuits' performance. Along the way it shows what BV can and cannot diagnose.

Skills applied

• Implementing BV and verifying deterministic output (§12.9).
• Using success probability as a fidelity proxy.
• Fitting an exponential error model to width-scaled data.
• Recognizing which error types BV is blind to.

Phase 1: The circuit

from qiskit import QuantumCircuit

def bernstein_vazirani(s):
    n = len(s)
    qc = QuantumCircuit(n + 1, n)
    qc.x(n); qc.h(n)                       # ancilla in |->
    qc.h(range(n))
    for i, bit in enumerate(reversed(s)):  # oracle: CX for each 1 in s
        if bit == '1':
            qc.cx(i, n)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

Two properties make it an ideal benchmark:

• Constant depth in $n$. The oracle's CNOTs all target the same ancilla but act on distinct controls, so with all-to-all connectivity the depth does not grow with $n$. Only the gate count grows.
• Deterministic output. The ideal result is s, always. Success probability is simply the fraction of shots equal to s.

Phase 2: Scaling data

Running with $s = 1010\ldots$ of increasing length, 8,192 shots each, on a heavy-hex device:

Note that CNOT count is half of $n$ because $s$ alternates — only the 1-bits generate a CNOT. This detail matters for the fit and is easy to overlook.

Phase 3: Fit an error model

Model success as independent per-operation survival:

$$P(n) = (1-\epsilon_{2q})^{g_2(n)} \cdot (1-\epsilon_{ro})^{n} \cdot (1-\epsilon_{1q})^{g_1(n)}$$

Readout is the dominant term because BV measures all $n$ qubits, so readout error enters with exponent $n$ while two-qubit error enters with exponent $n/2$.

Taking logs and fitting the two dominant contributions:

import numpy as np
from scipy.optimize import curve_fit

n   = np.array([4, 6, 8, 10, 12, 16, 20, 24])
P   = np.array([0.912, 0.857, 0.792, 0.735, 0.669, 0.548, 0.441, 0.353])
g2  = n / 2

def model(n, eps_2q, eps_ro):
    return (1 - eps_2q)**(n/2) * (1 - eps_ro)**n

popt, _ = curve_fit(model, n, P, p0=[0.007, 0.015])
print(f"eps_2q = {popt[0]:.4f},  eps_ro = {popt[1]:.4f}")

Fit result: $\epsilon_{2q} \approx 0.0071$, $\epsilon_{ro} \approx 0.0156$.

Compare against the backend's published calibration: median CNOT error $7.2\times10^{-3}$, median readout error $1.6\times10^{-2}$. The fit reproduces the device's own reported error rates to within a few percent from nothing but success-probability counts.

Finding 1. BV works as an in-situ calibration check. If the fitted rates disagree with published ones, either the published calibration is stale or something is wrong beyond the simple error model.

Phase 4: What BV cannot see

BV is a blunt instrument in three specific ways, and using it without knowing them produces false confidence.

Coherent errors partially cancel. A systematic over-rotation in the $H$ gates appears twice — before and after the oracle — and the second occurrence partially undoes the first. BV therefore under-reports coherent single-qubit error. Randomized benchmarking, which deliberately randomizes over the Clifford group, is the right tool for that.

It is insensitive to phase errors on idle qubits. The circuit is shallow, so qubits spend little time idle. A device with poor $T_2$ but good gates can look excellent under BV and fail on any deep circuit.

Its depth does not grow. BV stresses width and gate count, not depth. A device with good gates and short coherence will score well here and poorly on anything real. This is precisely why vendors like it, and precisely why a good BV number should never be quoted as evidence of algorithmic capability.

Finding 2. BV measures gate and readout error at scale. It says nothing about coherence-limited depth, which is the binding constraint for actual algorithms.

Phase 5: Using it well

A defensible benchmarking protocol:

1. Run BV across widths to fit $\epsilon_{2q}$ and $\epsilon_{ro}$, as above.
2. Cross-check against published calibration. Divergence is itself the signal.
3. Pair it with a depth-stressing benchmark — repeated identity circuits, or a mirror circuit — to characterize coherence separately.
4. Report the fitted rates, not the raw success probability. "BV succeeded 91% at $n=4$" is not portable; "$\epsilon_{2q} = 0.0071$" is.
5. Use the fitted model to predict a different circuit's fidelity, then measure it. A model that predicts is a model worth having; one that only describes the data it was fitted to is not.

Discussion Questions

1. Readout error enters with exponent $n$ and two-qubit error with $n/2$ for this choice of $s$. How would the fit change for $s = 111\ldots1$, and what does that suggest about benchmark design?
2. Coherent errors partially cancel in BV. Explain the mechanism and why randomized benchmarking avoids the problem.
3. BV's depth is constant in $n$. Argue for and against including it in a vendor benchmark suite.
4. The fit reproduced published error rates. What would you conclude if it returned rates twice as large?

Your Turn: Extensions

• Run BV for $s$ of all ones and all alternating bits at the same $n$; compare success probabilities and explain the gap.
• Add a variable-length idle delay before the final Hadamards and refit, extracting an effective $T_2$.
• Use the fitted parameters to predict GHZ-state fidelity at $n=5$, then measure it.
• Implement a mirror-circuit benchmark and compare what it reveals against BV.

Key Takeaways

• BV's benchmark value comes from its deterministic ideal output: every deviation is error, with no statistical modelling required.
• Fitting success probability against width recovers the device's two-qubit and readout error rates independently of vendor calibration data.
• Readout error usually dominates, since BV measures every qubit — the exponent is $n$, not $n/2$.
• BV is blind to coherent errors that cancel and to coherence-limited depth; a good BV score does not imply algorithmic capability.
• Report fitted error rates rather than raw success probabilities — the former transfer to other circuits, the latter do not.