Source-linked AI summary
Accrediting outputs of noisy intermediate-scale quantum computing devices
Samuele Ferracin, Theodoros Kapourniotis, Animesh Datta
TL;DR
Noisy operations make NISQ-device outputs unreliable, and gate-focused tests may not capture circuit-level noise. The paper uses trap circuits to accredit target-circuit outputs, providing a bound on the variation distance for accepted outputs while keeping implemented circuits no larger than the target.
Problem
NISQ devices have noisy state preparation, gates, and measurements, while gate-by-gate tests may miss temporal correlations and circuit-level noise.
Source: INTRODUCTION · p. 1Method
The authors use classically simulable trap circuits to test a target circuit, assuming bounded single-qubit-gate noise while allowing arbitrary noise in state preparation, entangling gates, and measurements.
Source: INTRODUCTION · p. 2Results
For accepted outputs, the protocol provides a confidence-qualified upper bound on variation distance between noisy and noiseless output distributions, with ε ∝ 1/v.
Source: INTRODUCTION · p. 2Takeaways & Limitations
Because every implemented circuit is no wider or deeper than the target and no noiseless device is required, the protocol is designed for practical NISQ-device accreditation.
Source: INTRODUCTION · p. 2The variation-distance bound applies only to accepted outputs; rejected runs receive no such bound.
Source: RESULTS · p. 4
Abstract
from arXiv · showhide
We present an accreditation protocol for the outputs of noisy intermediate-scale quantum devices. By testing entire circuits rather than individual gates, our accreditation protocol can provide an upper-bound on the variation distance between noisy and noiseless probability distribution of the outputs of the target circuit of interest. Our accreditation protocol requires implementation of quantum circuits no larger than the target circuit, therefore it is practical in the near term and scalable in the long term. Inspired by trap-based protocols for the verification of quantum computations, our accreditation protocol assumes that noise in single-qubit gates is bounded (but potentially gate-dependent) in diamond norm. We allow for arbitrary spatial and temporal correlations in the noise affecting state preparation, measurements and two-qubit gates. We describe how to implement our protocol on real-world devices, and we also present a novel cryptographic protocol (which we call `mesothetic' protocol) inspired by our accreditation protocol.
INTRODUCTION
Noisy operations make NISQ outputs unreliable, while gate-by-gate benchmarking can miss circuit-level noise and many cryptographic verification protocols remain experimentally challenging. The paper proposes trap-based circuit accreditation that bounds the variation distance for accepted outputs while using circuits no larger than the target.
INTRODUCTION
- Existing cryptographic protocols can verify outputs with minimal assumptions in principle, but their experimental implementations may require noiseless verifier devices or substantial extra resources.The paper contrasts such demands with its circuit-size-constrained accreditation protocol.Source: INTRODUCTION · pp. 1–2
- For accepted outputs, repeated protocol runs provide a confidence-qualified upper bound on variation distance between noisy and noiseless target-output distributions, with ε ∝ 1/v.The bound depends on the number of traps and applies to outputs from runs accepted by the protocol.Source: INTRODUCTION · p. 2
- All implemented circuits are no wider or deeper than the target, and the protocol requires no noiseless quantum device.Its single-qubit-gate noise assumption allows bounded, potentially gate-dependent errors; state preparation, entangling gates, and measurements may have arbitrary system-environment noise.Source: INTRODUCTION · p. 2
- Circuit-level testing can detect noise, including temporal correlations, that randomized benchmarking may miss or that appears only when preparation, gates, and measurements form a circuit.The protocol models noise on the joint system and environment and traces out the environment only at the end.Source: INTRODUCTION · pp. 1–2
- The authors also introduce a mesothetic verification protocol in which the verifier implements single-qubit gates while the prover performs the remaining operations.The verifier intervenes during circuit implementation, unlike prepare-and-send or receive-and-measure protocols.Source: INTRODUCTION · p. 2
RESULTS
The results establish bounds on how accepted target-circuit outputs deviate from noiseless outputs, using randomized traps under the stated repetition assumptions. They also show that Theorem 1 applies to unbounded gate-independent single-qubit noise, while extending Theorem 2 to weakly gate-dependent noise remains for future analysis.
Background
- The variation-distance guarantee applies only to the Nacc accepted runs among d repetitions with i.i.d. noise; outputs from rejected runs must be discarded.The bound uses the protocol’s theoretically computed ε and the experimentally observed Nacc.Source: RESULTS · pp. 3–4
Our accreditation protocol
- Without noise, the protocol always returns the correct target output and accepts it, because the QOTP cancels or is corrected and every trap outputs s=0.The output is accepted only when all traps give the correct outcome; otherwise it is rejected and discarded.Source: RESULTS · p. 5
The credibility of our protocol
- The QOTP converts even spatially and temporally correlated noise into classically correlated Pauli errors, and randomized trap gates detect those errors with probability greater than 1/4.Random H and S gates help prevent errors from canceling, while randomized endpoint Hadamards address measurement errors.Source: RESULTS · pp. 5–6
- With noiseless single-qubit gates and at least three traps, the protocol accredits outputs despite arbitrary noise in state preparation, measurements, and two-qubit gates, with ε=κ/(v+1) and κ≈1.7.The result follows because traps detect arbitrary Pauli errors with probability greater than 1/4.Source: RESULTS · p. 6
- With v≥3 traps and bounded single-qubit gate noise, the protocol bounds accreditation error by ε=gκ/(v+1)+1−g, where κ≈1.7 and g reflects gate reliability.If the single-qubit error rate r0 ≪ 1/[m(v+1)], then g≈1 and ε≈1.7/(v+1).Source: RESULTS · pp. 6–7
RESULTS
- With unbounded but gate-independent single-qubit noise, Theorem 1 still gives ε = κ/(v + 1).The noise can be factored into the CZ noise, allowing the same proof arguments as in Theorem 1.Source: RESULTS · p. 7
- The authors expect Theorem 2 to extend to weakly gate-dependent single-qubit noise, as in some randomized-benchmarking protocols, but leave its analysis to future work.Source: RESULTS · p. 7
5. Mesothetic verification protocol:
The mesothetic protocol adapts the accreditation protocol to cryptographic verification, but requires the verifier to handle all n qubits and apply single-qubit gates. It is not blind in its basic form; a blind variant is possible at the cost of increased circuit depth.
5. Mesothetic verification protocol:
- Alice must receive all n qubits from Bob, apply single-qubit gates, and return them to verify an n-qubit computation.The cryptographic protocol's soundness parameter εcr is the probability that Alice accepts a wrong target output when Bob cheats.Source: §5 · p. 7
- Unlike prepare-and-send or receive-and-measure protocols, Alice applies the quantum one-time pad during circuit implementation, requiring an n-qubit quantum memory.The protocol is more demanding than cited protocols that require only a single-qubit memory.Source: §5 · p. 7
- The basic protocol is not blind: Alice reveals information such as two-qubit-gate positions, while security relies on Bob being unable to distinguish target and trap circuits.The relevant hidden quantity is v0, the target-circuit position.Source: §5 · p. 7
- A blind variant recompiles the target into a normal-form circuit with fixed cZ gates, increasing circuit depth and trading away the protocol's minimal overhead.The brickwork-type circuit in Figure 6 is given as an example.Source: §5 · p. 7
DISCUSSION
The discussion describes how repeated accepted runs and acceptance probability support bounds on the distance between noisy and noiseless outputs. It also identifies practical limits from circuit size and single-qubit-gate noise, alongside open questions about fault tolerance and the verifier's requirements in the mesothetic protocol.
DISCUSSION
- After repeated runs with the same target and trap count, accepted outputs under i.i.d. noise can be bounded in variation distance from noiseless outputs.Each run accepts or rejects the target output; rejected outputs are discarded.Source: DISCUSSION · p. 8
- The real-device bound depends on ε from Theorems 1 and 2 and on the protocol's acceptance probability, which is estimated by repeated device runs.Some noise models permit analytic lower bounds on acceptance probability and thus upper bounds on variation distance.Source: DISCUSSION · p. 8
- For present NISQ error rates, the authors expect worthwhile bounds for targets around 7 qubits and 7 bands, while larger circuits may yield unusably large bounds or no accepted runs.Large bounds still indicate high noise and that device outputs are not credible.Source: DISCUSSION · p. 8
- Theorem 2 requires single-qubit-gate error rates to decrease as target-circuit size grows, a requirement the authors identify as an obstacle to scalable quantum computing.They note incorporating fault tolerance into existing protocols as one strategy used in prior work.Source: DISCUSSION · p. 8
- Interfacing fault tolerance with accreditation remains an open challenge, including defining verifiable fault tolerance through acceptability and detectability.Source: DISCUSSION · p. 9
- The current analysis does not cover unbounded gate-dependent single-qubit noise, including over- or under-rotations, because the QOTP is applied at the single-gate level.The authors describe this as an open question for the protocol.Source: DISCUSSION · p. 9
- The mesothetic verifier needs an n-qubit memory and single-qubit gates, unlike several cited protocols that need only single-qubit memory.Whether a mesothetic protocol can use only single-qubit gates and memory remains open.Source: DISCUSSION · p. 9
METHODS
The methods describe an accreditation protocol that selects one target circuit among trap circuits, uses randomized single-qubit operations, and outputs the target result with an acceptance flag. The protocol has no quantum overhead and uses O(nm) classical bits per computation.
METHODS
- The protocol has no quantum overhead because every circuit is the same size as the circuit being verified; its classical overhead is O(nm) bits per computation.The target uses 2nm + n random bits, while traps use at most 2nm + n + nm bits.Source: METHODS · p. 9
- The target is an n-qubit circuit with single-qubit gates and cZ gates in m bands, ending in Pauli-X measurements; the protocol also takes the number of traps as input.Source: METHODS · p. 9
- Routine 1 is labeled the quantum one-time pad and uses random bits to construct single-qubit gates for the circuits.Source: METHODS · p. 9
- Trap circuits are constructed with randomized S and H gate choices across bands, with inverse single-qubit gates applied between successive bands.The routine also randomizes endpoint gates using a bit t.Source: METHODS · p. 10
- Alice randomly selects one of v + 1 circuits as the target and prepares the remaining circuits as traps; the protocol returns the target output and an acceptance flag.The flag is set to reject when a trap output fails its check.Source: METHODS · pp. 9–10
- In the mesothetic procedure, Bob sends the qubits to Alice for single-qubit gates and receives them back before applying the target's cZ gates.Bob creates n qubits in |+⟩, then measures in the Pauli-X basis and communicates the outputs to Alice.Source: METHODS · p. 10
Appendix A: Statement and Proof of Lemma 1
Lemma 1 reduces the specified noise in state preparation, measurements, and two-qubit gates to classically correlated Pauli errors. The reduction assumes noiseless single-qubit gates and uses Pauli twirling across circuit operations.
Appendix A: Statement and Proof of Lemma 1
- With noiseless single-qubit gates, noise of type N1 becomes classically correlated Pauli errors at state preparation, before entangling gates, and before measurements.State-preparation and measurement errors are restricted to Pauli Z; entangling-gate errors may be X, Y, or Z.Source: Appendix A · p. 13
- The proof uses the Pauli Twirl and a restricted Pauli Twirl [29] to eliminate off-diagonal terms and obtain a mixture of Pauli-error processes.The Pauli-X components at input and measurement can be ignored because they stabilize the relevant states or measurements.Source: Appendix A · pp. 13, 15, 16
- For one circuit with two entangling bands, the resulting state is a convex combination indexed by Pauli errors before preparation, between bands, and before measurement.The component errors at preparation and measurement are in {I, Z}⊗n, while the intermediate errors are in {I, X, Y, Z}⊗n.Source: Appendix A · p. 17
- The argument extends to more bands and multiple circuits by deferring measurements and preparing all circuits’ inputs at the start.For multiple circuits, the proof uses their serial implementation and applies the same twirling argument to the joint state.Source: Appendix A · pp. 17–18
Appendix B: Statement and Proof of Lemma 2
Lemma 2 bounds the probability that a trap outputs the correct string under any collection of Pauli errors. Its proof handles single-band and multi-band error patterns by reducing them to simpler patterns.
Appendix B: Statement and Proof of Lemma 2
- For any Pauli-error collection affecting a trap, averaging over its possible single-qubit gates bounds the probability of output s = 0 by 3/4.Equivalently, every such collection is detected with probability at least 1/4.Source: Appendix B · p. 18
- Single-band error collections yield s = 0 with probability below 1/2, while merging two errors reduces two-band collections to single-band errors or cancellation.The cancellation probability is at most 1/2, giving the 3/4 bound for two-band collections.Source: Appendix B · pp. 18–19
- The same bound covers all four two-band placements: preparation-to-entangling, entangling-to-measurement, two entangling bands, and preparation-to-measurement.For preparation-to-measurement errors, random cX orientations make commuting Pauli-Z errors change randomly, yielding detection probability above 1/2.Source: Appendix B · pp. 20–21
Appendix C: Proof of Theorem 1
The proof bounds accreditation error by considering how many circuits are affected by Pauli noise and how likely affected traps are to pass. Optimizing that bound yields an inverse scaling with the number of traps plus one.
Appendix C: Proof of Theorem 1
- Because Pauli-error probabilities do not depend on the single-qubit gates, the target is among b_v noise-affected circuits with probability b_v/(v + 1).The random target position and trap parameters therefore do not change the probability assigned to each error collection.Source: Appendix C · p. 22
- If b_v − 1 traps are affected, their joint probability of all outputting s = 0 is at most (3/4)^(b_v−1).This applies Lemma 2’s per-trap bound to the traps affected by the error collection.Source: Appendix C · p. 22
- For v ≥ 3, the error bound is maximized when b_v = 3, yielding an upper bound κ/(v + 1), with κ ≈ 1.7.The stated bound is obtained after summing over possible Pauli-error collections.Source: Appendix C · p. 23