PaperlayerView exact revision on arXiv

Source-linked AI summary

Theory of quantum system certification: a tutorial

Martin Kliesch, Ingo Roth

arXiv:2010.05925v3quant-ph

TL;DR

Complex quantum devices are difficult to certify because their behavior challenges classical simulation, motivating protocols suited to near-term systems. This tutorial presents physical-layer certification methods for quantum states and processes, together with mathematical tools for rigorous guarantees, while noting that application-level verification and broader property-specific methods lie outside its scope.

  • Problem

    The paper addresses how to certify the correct functioning of complex quantum devices when classical simulation-based strategies become impractical.

  • Method

    The tutorial surveys state- and process-certification protocols and develops common mathematical methods for deriving their theoretical performance guarantees.

  • Results

    The tutorial organizes and explains direct state certification, fidelity estimation, process certification, randomized benchmarking, and cross-entropy benchmarking for near-term quantum devices.

  • Takeaways & Limitations

    Physical-layer certification remains important for diagnosing components of complex quantum devices during development and runtime.

Abstract

from arXiv · show

The precise control of complex quantum systems promises numerous technological applications including digital quantum computing. The complexity of such devices renders the certification of their correct functioning a challenge. To address this challenge, numerous methods were developed in the last decade. In this tutorial, we explain prominent protocols for certifying the physical layer of quantum devices described by quantum states and processes. Such protocols are particularly important in the development of near-term devices. Specifically, we discuss methods of direct quantum state certification, direct fidelity estimation, shadow fidelity estimation, direct quantum process certification, randomized benchmarking and cross-entropy benchmarking. Moreover, we provide an introduction to powerful mathematical methods, which are widely used in quantum information theory, in order to derive theoretical guarantees for the protocols.

I. INTRODUCTION

Quantum certification addresses the difficulty of validating complex devices when classical simulation and full tomography become impractical. This tutorial organizes certification protocols by their assumptions, resource demands, information gain, physical abstraction layer, and mathematical guarantees.

  • Motivation: Complex quantum devices are difficult to certify because their behavior can quickly exceed available classical simulation resources.The complexity that enables quantum technology also obstructs straightforward certification strategies.
  • Protocol landscape: Certification protocols vary in assumptions and resource requirements, reflecting settings from detailed small-device studies to lightweight remote-server verification.The tutorial surveys this landscape rather than treating certification as a single task with uniform requirements.
  • Scope: The tutorial presents estimation-based protocols for quantum states and processes and introduces shared mathematical tools for proving rigorous performance guarantees.Most estimation protocols can be converted into epsilon-certification protocols by a standard method.
  • Protocol anatomy: Certification protocols conceptually involve the device, a measurement apparatus, and a classical processor, although the division and assumptions can vary.The measurement apparatus is typically assumed more precisely characterized, while device-independent protocols combine quantum components into one unassumed device.
  • Protocol landscape: Protocols can be compared by device assumptions, measurement and sample complexity, and the information gained about the allowed device hypothesis class.Information gain can trade off against protocol complexity, and analyzing it can yield lower bounds on certification complexity.
  • Scope: NISQ devices motivate scalable physical-layer certification because full tomographic characterization is infeasible at their complexity, while fault-tolerant scalability remains a future step.The tutorial focuses on noisy, intermediate-size devices and does not cover application-level verification methods.

B. A definition of quantum state certification

Quantum state certification tests whether repeated preparations approximate a chosen target state within a specified distance tolerance, using measurements and classical post-processing. Their practical demands include sampling, measurement, and classical-processing complexity, while assumptions such as iid preparation and structured targets affect guarantees and efficiency.

  • Certification task: Quantum state certification tests whether a repeatedly prepared state ˜ρ approximates a target state ρ within tolerance ϵ, outputting “accept” or “reject” from measurement data.The test uses a quantum measurement on device output followed by classical post-processing.
  • Certification task: An ϵ-certification test requires completeness for target preparations and soundness when dist(˜ρ, ρ) > ϵ.The statistical formulation treats these requirements as bounded type-II and type-I errors, respectively.
  • Assumptions: Certification guarantees may require independent preparation, while the stronger iid assumption can fail under environmental drift and may be removed only with higher measurement effort.The tutorial notes that de Finetti-based or improved analyses can relax iid assumptions at additional measurement cost.
  • Complexity: Sampling complexity is the scaling of prepared-state copies with d and ϵ; for n-qubit systems, O(polylog(d)) corresponds to O(poly(n)) sampling.The tutorial identifies sampling complexity as a central measure of certification-test complexity.
  • Complexity: Measurement complexity concerns how measurements are implemented, including simultaneous-copy requirements, adaptivity, and circuit complexity.The presented state-certification protocols use sequential measurements on individual copies, avoiding the need to store copies before measurement.
  • Efficiency: Full tomography can require at least 2^n measurements for pure n-qubit states, whereas fidelity estimation and certification can use dramatically fewer measurements for structured targets.Certification may also improve the ϵ-dependence of sample complexity relative to fidelity estimation.

D. Expectation value estimation for observables

Observable expectation values are estimated from repeated measurements, with sampling guarantees derived from bounded outcomes and concentration inequalities. The resulting measurement effort can be independent of Hilbert-space dimension, while multiple-observable estimation and shadow methods differ in measurement-setting requirements.

  • An observable is a self-adjoint operator whose projective measurement produces eigenvalue outcomes with probabilities determined by the state.
  • Expectation values cannot be observed directly and are estimated using the empirical mean of repeated single-copy measurements.
  • Independent measurements of bounded observables allow Hoeffding-based sampling-complexity guarantees for estimating expectation values to accuracy ϵ and confidence 1−δ.
  • The measurement effort for estimating bounded-observable expectation values is independent of Hilbert-space dimension, while confidence improves exponentially with additional measurements.
  • Expectation-value estimation can induce certification tests for distance measures defined through observable expectations, while norm inequalities support the mathematical analysis of state distinguishability.
  • Estimating multiple observables separately requires multiple measurement settings, whereas shadow estimation can estimate multiple observables from a single setting for certain observables.

F. Direct quantum state certification

Direct quantum state certification uses measurement protocols that directly output accept or reject rather than embedding another estimation task. For pure targets, guarantees depend on confidence, infidelity tolerance, and the measurement operator’s spectral gap, while implementability motivates probabilistic strategies.

  • Direct certification protocols target an accept/reject certification test without using another protocol, such as estimation, as a subroutine.
  • For a pure target, projecting directly onto the target accepts it with probability one and provides an infidelity certification guarantee from repeated samples.
  • The direct protocol’s sample complexity is independent of physical system size, but implementing the target-state POVM may be impractical for many states.
  • Probabilistic measurement strategies replace an inaccessible target projection with randomly selected feasible POVM elements and an effective measurement operator.
  • A no-false-rejection constraint requires every feasible measurement element to pass the target state with probability one.
  • The minimax strategy can be optimized over physically available measurements, including unrestricted measurements and Pauli-restricted settings.
  • With a positive spectral gap, the feasible-strategy protocol certifies a pure target with confidence at least 1−δ, accepts the target with probability one, and retains the direct protocol’s scaling when the gap is constant.

1. Stabilizer states

Stabilizer states are uniquely specified by the joint +1 eigenspace of an Abelian Pauli subgroup. Uniformly sampling their nontrivial stabilizer observables yields a minimax-optimal Pauli certification strategy with a constant-overhead guarantee.

  • 1. Stabilizer states: An n-qubit stabilizer state is the unique joint eigenvalue-1 state of an Abelian subgroup of the Pauli group generated by n elements.
  • 1. Stabilizer states: The stabilizer group contains 2^n elements, including the identity, and excludes the element −1.
  • 1. Stabilizer states: Uniformly measuring the nontrivial stabilizer observables is minimax optimal among strategies based on accessible Pauli observables.
  • 1. Stabilizer states: For each nontrivial stabilizer, the projector onto its positive eigenspace defines a two-outcome Pauli measurement.
  • 1. Stabilizer states: The resulting effective measurement operator preserves the target state and has a specified second-largest eigenvalue, determining its spectral gap.
  • 1. Stabilizer states: Restricting from arbitrary measurements to Pauli measurements incurs at most a constant overhead, while only randomly subsampled stabilizer observables need be measured.

2. Extension towards fidelity estimation

Direct certification can be extended to fidelity estimation when the effective measurement operator is homogeneous in the target state. Estimating its expectation value then yields fidelity information, but requires sampling effort that scales quadratically with inverse additive accuracy.

  • Direct certification provides only accept/reject information, whereas fidelity estimation explicitly quantifies the distance between an implementation and its target.
  • When the effective measurement operator is homogeneous, its expectation value determines the fidelity between the prepared and target states.
  • Estimating the effective operator’s expectation to additive error ε requires measurement effort scaling as 1/ε^2.
  • For stabilizer states, the measurement family can be exponentially large, motivating Monte Carlo and importance-sampling methods for efficient estimation.

Further reading

Further reading surveys extensions of quantum-state certification across specialized state families and adversarial settings, then develops direct fidelity estimation using importance sampling. DFE provides unbiased, confidence-controlled fidelity estimates with favorable sampling complexity under stated conditions.

  • Extensions of direct certification: Direct certification has been extended to maximally entangled, stabilizer, matrix-product, permutationally invariant, ground, hypergraph, Dicke, graph, and adversarially prepared states.The listed protocols cover both restricted state families and scenarios without identical-and-independent preparation assumptions.
  • Extensions of direct certification: Ground-state certification uses efficient protocols and fidelity witnesses to estimate fidelity lower bounds from simple measurements.These methods include ground states of locally interacting Hamiltonians, including states enabling universal quantum computation.
  • Extensions of direct certification: Global von Neumann measurements on multiple iid. copies yield an ϵ-certification version with sample complexity scaling as O(d/ϵ).The setting includes mixed target states.
  • Direct fidelity estimation: Direct fidelity estimation samples Pauli measurements from a target-dependent importance distribution, emphasizing terms particularly relevant to the fidelity.The protocol combines classical sampling of Pauli products with repeated measurements estimating their characteristic functions.
  • Direct fidelity estimation: Importance sampling can reduce variance, but the exactly optimal distribution requires a normalization factor whose calculation is equivalent to solving the original integration problem.Non-optimal but effective choices can nevertheless accelerate integration.
  • Direct fidelity estimation: The DFE estimator is unbiased, and iid. preparations yield an ϵ-accurate estimate with confidence 1 −δ for well-conditioned states.For general pure targets, the stated guarantee is 2ϵ accuracy with confidence 1 −2δ.
  • Direct fidelity estimation: DFE sample complexity scales linearly in Hilbert-space dimension, whereas tomography requires ˜Ω(d2 rank(˜ρ)2) Pauli measurements.For well-conditioned states, the sampling complexity is independent of system size.

I. Random states and unitaries

Random states and unitaries are analyzed through moment operators associated with Haar measures. These operators are characterized as orthogonal projectors onto commutants, linking integration over random unitaries to representation theory.

  • Haar-random unitaries: The Haar measure on U(d) provides a canonical probability distribution for random unitary operations used in quantum-information protocols.Random unitaries combined with fixed measurements can rapidly provide information about an entire state space.
  • Haar moment operators: The Haar k-th moment operator enables expectation values of arbitrary degree-k polynomials in U and U† to be calculated by linear contraction.The moment operator therefore converts polynomial averaging into an algebraic operation.
  • Haar moment operators: The k-th Haar moment operator commutes with every k-fold tensor power of a unitary and is the orthogonal projector onto the corresponding commutant.This characterization follows from Haar invariance and orthogonality under the Hilbert-Schmidt inner product.
  • Generalization: The commutant characterization applies more generally to arbitrary groups equipped with Haar measure, including uniform measures on finite groups.The same projector argument extends beyond the unitary group.

1. Representation theory

Representation theory supplies the structural tools used to analyze random-unitary moments. The section introduces irreducibility, invariant subspaces, Schur’s lemmas, and Schur-Weyl duality for commuting unitary and permutation actions.

  • Representation basics: A representation decomposes into irreducible representations, while repeated equivalent irreducibles form multiplicity spaces; multiplicity-free decompositions contain no equivalent irreducible pairs.Invariant subspaces provide the iterative mechanism for decomposing finite-dimensional representations.
  • Schur’s lemmas: Schur’s lemma states that an operator commuting with an irreducible representation is scalar, and an intertwiner between irreducible representations is either zero or establishes unitary equivalence.The scalar conclusion follows because eigenspaces of a commuting operator are invariant.
  • Schur’s lemmas: Every irreducible representation of an Abelian group is one-dimensional.Each group element acts as a scalar, making every subspace invariant; irreducibility then forces dimension one.
  • Schur-Weyl duality: The diagonal U(d) action on (C^d)^⊗k commutes with the symmetric-group action that permutes tensor factors.This commuting pair is the starting point for Schur-Weyl duality.
  • Tensor subspaces: Symmetric and antisymmetric tensor subspaces are defined by invariance and sign changes under permutations, with orthogonal projectors onto each subspace.For k=2, these subspaces correspond to the familiar symmetric and antisymmetric matrix parts.
  • Schur-Weyl duality: Schur-Weyl duality states that the two commuting representations span each other’s commutants and yield a multiplicity-free decomposition indexed by partitions of k.The decomposition separates Weyl modules, acted on by U(d), from Specht modules, acted on by S_k.
  • Applications to moments: Schur-Weyl duality characterizes the Haar k-moment operator as an orthogonal projector onto the span associated with the symmetric-group action.This connects the moment calculation to the permutation representation.

3. Uniformly random state vectors

Uniform random state vectors and unitary designs provide tractable alternatives for calculating low-degree moments. Their moment operators are governed by symmetric-subspace projectors, while designs reproduce selected Haar moments with structured ensembles.

  • Uniform random states: Uniform pure states can be generated from the complex sphere or identified with pure density matrices in complex projective space.Both descriptions carry unitarily invariant probability distributions.
  • State moments: Moments of degree-k polynomials in a uniformly random state reduce to contractions involving the k-fold state projector and the symmetric-subspace projector.The moment operator is proportional to the symmetric projector, with normalization determined by its dimension.
  • Unitary designs: A unitary k-design is a distribution whose k-th moment operator matches the Haar moment operator, and a uniform finite subset can satisfy the same condition.A k-design is also a (k−1)-design.
  • Unitary designs: The Clifford group is a unitary 3-design but not a unitary 4-design.Consequently, for k>3 its commutant is strictly larger than the span of the permutation group.
  • Examples: Maximal sets of mutually unbiased bases and SIC POVMs are examples of structured state ensembles with design properties.Maximal MUB sets are spherical 2-designs, while SIC POVMs are 2-designs.

J. Shadow fidelity estimation

Shadow fidelity estimation reconstructs an incomplete state description from randomized measurements and uses it to estimate fidelity to a pure target state. With unitary 3-designs and a median-of-means estimator, it achieves dimension-independent sampling complexity.

  • Protocol: SFE estimates fidelity by applying random unitaries, performing basis measurements, and aggregating the resulting estimators with a median-of-means procedure.The protocol draws Ui from a design, measures each prepared state, and outputs the median of means of the resulting values.
  • Guarantee: For a pure target state and a unitary 3-design, the estimator is unbiased and ϵ-accurate with confidence 1−δ.The guarantee applies to ñρ independent state preparations, with the median formed from blocks of k = ⌈8 ln(1/δ)⌉ samples.
  • Comparison: For arbitrary pure target states, SFE’s required number of state copies does not depend on the Hilbert-space dimension.Efficient classical post-processing can still require additional structure, such as stabilizer states.
  • Analysis: The estimator has variance below 5, avoiding the dimension-dependent bounds that would make direct use of Hoeffding’s inequality ineffective.The variance is taken over both the random unitary and the subsequent measurement outcome.
  • Sampling complexity: ñρ ≥ 160 ϵ^-2 ln(1/δ) state preparations suffice for the stated accuracy and confidence guarantee.This condition follows by combining the unbiasedness and variance bounds with the median-of-means estimator.

Further reading

The tutorial connects state-certification methods to quantum-process certification through channel representations, Choi states, and related mathematical structure. It also motivates randomized benchmarking as a SPAM-robust approach and introduces the formal conditions defining quantum channels.

  • Process certification: Quantum-process certification can be obtained by certifying outputs on suitable input states or by using the Choi-Jamiołkowski isomorphism to represent processes as states.The tutorial then translates direct state-certification methods to quantum processes.
  • Challenges: Direct process characterization is vulnerable to state-preparation and measurement errors, while self-consistent methods require extensive measurements, sampling, and post-processing.These methods also provide more information than certification requires.
  • Randomized benchmarking: Randomized benchmarking estimates gate performance by measuring error accumulation across random gate sequences of different lengths and is robust against SPAM errors.The method studies how the measured error depends on sequence length.
  • Quantum channels: A quantum channel is a completely positive and trace-preserving map, with complete positivity requiring positivity even after extension by an identity map.The tutorial distinguishes completely positive maps from the subset that is also trace preserving.
  • Choi representation: The Choi matrix characterizes channel properties: trace preservation, Hermiticity preservation, and complete positivity correspond to stated conditions on the matrix.In particular, complete positivity is equivalent to positive semidefiniteness of the Choi matrix.

2. Inner products of superoperators and fidelity measures

The tutorial relates superoperator inner products to fidelity measures for quantum processes. Average gate fidelity provides an average-case comparison, while related quantities connect to Choi matrices, Frobenius norms, and channel distance measures.

  • Choi and Frobenius representations: The Hilbert-Schmidt inner product of superoperators equals the inner product of their corresponding Choi matrices.The same framework connects average gate fidelity to the Frobenius norm, which acts as an average-case error measure.
  • Average gate fidelity: Average gate fidelity compares two maps by averaging their action on pure input states.It is defined using the Haar-invariant distribution over pure state vectors.
  • Infidelity: For unital completely positive X and quantum channels Y, average infidelity is nonnegative and vanishes exactly when X = Y.This gives infidelity a distance-like interpretation under the stated assumptions.
  • Relations between measures: For trace-preserving and unital channels, average gate fidelity and the Hilbert-Schmidt inner product are affinely related with proportionality scaling O(d^-2).The tutorial also identifies related fidelity parameters used in randomized-benchmarking analysis.

3. The diamond norm

The diamond norm measures worst-case operational distinguishability of quantum channels, including the use of ancillary systems. The tutorial contrasts this worst-case quantity with average infidelity and describes conditions under which the dimensional and square-root penalties can be improved.

  • Operational meaning: The diamond norm captures the maximum distinguishability of two channels when arbitrary ancillary systems and entangled inputs are allowed.Optimal distinguishability can be achieved with an ancillary space whose dimension equals that of the input space.
  • Structural properties: For Hermitian-preserving maps, the diamond-norm supremum is attained on a pure density operator, and channel outputs remain normalized when the map is trace preserving.The norm also has stability, tensor-product multiplicativity, and product sub-multiplicativity properties.
  • Choi-state comparison: Distinguishing channels through their Choi states is generally not optimal, because Choi-state trace distance can differ from diamond distance.The tutorial gives inequalities relating the two quantities and notes that the bounds can be tight.
  • Unitary channels: For unitary channels, diamond distance is determined by the spectrum of the unitary difference U†V and a convex-hull optimization in the complex plane.This gives a simpler computation than the general semidefinite-program formulation.
  • Infidelity bounds: The general infidelity-to-diamond-norm upper bound carries a dimensional factor O(d), while its lower-bound behavior involves square-root scaling in infidelity.The dimensional factor can become O(2^n) for n qubits, and small-system certification may therefore require much smaller infidelity.
  • Improved worst-case bounds: For unital channels, diamond distance scales as O(r(X)) when the unitarity satisfies u(X) = umin + O(r^2(X)).Channels saturating the relevant lower bound exhibit linear diamond-distance scaling in infidelity.

B. Direct quantum process certification

Quantum process certification can be obtained by certifying a process’s Choi state, while randomized benchmarking extracts process-quality information through sequence-dependent decay. The tutorial also describes assumptions, implementation forms, and limitations governing these protocols.

  • Direct quantum process certification: Process certification lifts state-certification methods through the Choi–Jamiołkowski isomorphism by preparing and certifying the process’s Choi state.For Clifford channels, the Choi state is a stabilizer state, enabling direct certification methods.
  • Direct quantum process certification: For suitable measurement strategies, process certification can use prepare-and-measure schemes instead of entanglement with ancillary systems.The implementation prepares an input state, applies the channel under scrutiny, and measures a dichotomic POVM on the output.
  • Direct quantum process certification: The direct Clifford-process test certifies the Choi state with respect to infidelity, accepts the target with probability 1, and corresponds to entanglement gate-infidelity certification.The cited proposition states that the test uses independent state preparations and can be implemented as a prepare-and-measure scheme.
  • Direct quantum process certification: Fidelity-estimation protocols extend to processes by applying the process to randomly chosen input states and estimating the fidelity of the outputs.The original direct fidelity-estimation proposal includes quantum channels using input states sampled from eigenstates of multiqubit Pauli operators.
  • Randomized benchmarking: Randomized benchmarking reduces sensitivity to SPAM errors by applying the process in sequences of different lengths and fitting their measurement decay.Under a unitary 2-design, twirling maps a trace-preserving channel to a depolarizing channel characterized by an effective depolarizing parameter.
  • Randomized benchmarking: The RB decay parameter estimates the effective depolarizing parameter and therefore the average gate fidelity, while SPAM errors enter only the fitting constants A and B.Rigorous guarantees are involved because measurement and sequence-subsampling errors propagate through exponential fitting, whose behavior depends on the algorithm and sequence lengths.

Interleaved randomized benchmarking

Interleaved randomized benchmarking supplements standard randomized benchmarking with sequences that insert a target gate, using both decay parameters to estimate the target gate’s effective depolarizing behavior under stated noise assumptions.

  • Certification: Under additional assumptions, combining both decay parameters yields an estimate of the target gate’s effective depolarizing parameter and average gate fidelity.The resulting certificate concerns average performance of an individual quantum gate.
  • Protocol: Interleaved randomized benchmarking inserts a fixed target gate between randomly drawn group gates and computes the inverse relative to the modified sequence.The protocol outputs decay parameters from both the standard and interleaved experiments.
  • Assumptions: The analysis assumes a mostly gate-independent noise model, with a common noise channel after non-target gates and a unitary 2-design gate set.The target gate is treated separately from the shared noise model.
  • Analysis: The standard experiment estimates the effective depolarizing constant of the group-average error channel, while the interleaved experiment estimates the corresponding quantity for the target gate concatenated with that channel.The latter decay follows a single-exponential fitting model under the stated assumptions.
  • Certification: Controlling or estimating the noise unitarity can tighten error bounds and provide worst-case performance bounds from average gate fidelities.The systematic error is small when the noise is decoherent, satisfying u(Λ) ≈ p(Λ)^2.

Further reading

The tutorial situates randomized benchmarking and cross-entropy benchmarking within broader certification developments, emphasizing extensions to flexible gate sets, richer diagnostics, and sampling-task verification.

  • Randomized benchmarking: Randomized benchmarking began with unitary and Clifford groups, while later analyses addressed gate-dependent noise and broader fitting models.A general framework controls subdominant Fourier contributions using a diamond-norm closeness condition to a reference representation.
  • Randomized benchmarking: Flexible randomized benchmarking protocols support groups beyond unitary 2-designs, where multiple irreducible representations can produce multiple decay rates.Variants isolate different decays by state preparation or by combining data from several experiments.
  • Randomized benchmarking: Interleaved randomized benchmarking was refined with unitarity-based bounds, and combining relative gate fidelities can provide tomographic information about error channels.These tomography schemes can be resource optimal for unitary and Clifford gates under SPAM-robust data.
  • Randomized benchmarking: Randomized benchmarking extensions include nonuniform sequence distributions, leakage characterization, loss, addressability, cross-talk, unitarity, and logical-level operations.Drawing sequences from generating gates can reduce the required sequence lengths.
  • Cross-entropy benchmarking: Cross-entropy benchmarking was used in quantum-supremacy experiments to assess fidelity measures or certify sampling from a specific circuit’s output distribution.Its measures compare probability distributions at the application layer rather than only characterizing the physical layer.
  • Cross-entropy benchmarking: Sampling-task verification requires a protocol that guarantees implementation of the correct distribution, but non-interactive black-box verification from samples alone is not efficiently available classically.The same distribution features that support classical hardness also hinder efficient verification from samples.

Cross-entropy benchmarking protocol

Cross-entropy benchmarking estimates distribution-comparison measures by evaluating ideal circuit probabilities on experimental samples. Its guarantees rely on probability-distribution structure and classical computability, limiting direct use for circuits beyond classical simulation.

  • Protocol: Cross-entropy benchmarking computes ideal probabilities for experimentally observed outcomes and averages a function of those probabilities to estimate cross-entropy fidelity or cross-entropy.The relevant functions are f_F(p)=d p−1 for cross-entropy fidelity and f_H(p)=−ln(p) for cross-entropy.
  • Protocol: The protocol requires a classical computer to calculate individual probabilities of the circuit for each observed outcome.Consequently, it is applied directly to circuits that remain classically simulable, with extrapolation used for harder regimes.
  • Guarantees: For Haar-random or Porter–Thomas-like circuits, exponentially suppressed large probabilities support bounds on the sampling complexity of linear cross-entropy estimation.The proof bounds the estimator’s range and applies Hoeffding’s inequality after establishing a high-probability bound on ideal probabilities.
  • Guarantees: Estimating cross-entropy requires an additional lower-tail analysis because the logarithm is not bounded using only the available upper bound on ideal probabilities.The tail distribution must be calculated explicitly to control the estimator’s random variables.
  • Derived measures: Cross-entropy estimates can be shifted to obtain cross-entropy difference, analytically for sufficiently Haar-like circuits or numerically from computed ideal probabilities.For a Porter–Thomas ideal distribution, the cross-entropy difference relates to cross-entropy fidelity through D_XE(q,p)=1−d_XE(q,p).
  • Limitations: Cross-entropy alone does not imply a total-variation-distance bound without additional assumptions, although Pinsker’s inequality relates total variation to KL divergence.The KL divergence also requires estimating the entropy of the implemented distribution, which XEB does not directly provide.
Loading 2010.05925v3…