PaperlayerView exact revision on arXiv

Source-linked AI summary

Certified randomness using a trapped-ion quantum processor

Minzhao Liu, Ruslan Shaydulin, Pradeep Niroula, Matthew DeCross, Shih-Han Hung, Wen Yu Kon, Enrique Cervero-Martín, Kaushik Chakraborty, Omar Amer, Scott Aaronson, Atithi Acharya, Yuri Alexeev, K. Jordan Berg, Shouvanik Chakrabarti, Florian J. Curchod, Joan M. Dreiling, Neal Erickson, Cameron Foltz, Michael Foss-Feig, David Hayes, Travis S. Humble, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Michael Mills, Steven A. Moses, Brian Neyenhuis, Shaltiel Eloul, Peter Siegfried, James Walker, Charles Lim, Marco Pistoia

arXiv:2503.20498v1quant-phcs.CRcs.ET

TL;DR

The paper addresses how an untrusted remote quantum device can generate randomness with a certifiable entropy guarantee. It develops and experimentally implements an RCS-based protocol with classical verification, analyzing security against a restricted adversary. The experiment certifies 71,313 bits of entropy under the stated assumptions, while finite-size and protocol differences limit direct applicability of the asymptotic guarantees.

  • Problem

    Certified randomness must be generated and verified despite an untrusted server, but existing entropy guarantees and asymptotic analyses do not directly cover this finite, distinct-circuit setting.

  • Method

    The paper extends RCS-based entropy analysis to independently sampled circuits and implements a protocol whose security is analyzed against a restricted adversary.

  • Results

    71,313 bits of entropy are certified in the experiment under the stated restricted-adversary model and assumptions.

  • Takeaways & Limitations

    The results provide a demonstrated route toward certified randomness using a near-term quantum processor and classical verification.

  • Takeaways & Limitations

    The finite experiment is not asymptotic, relevant constants are unknown, and the implemented and analyzed protocols differ; the adversarial assumptions may also be stronger than necessary.

Abstract

from arXiv · show

While quantum computers have the potential to perform a wide range of practically important tasks beyond the capabilities of classical computers, realizing this potential remains a challenge. One such task is to use an untrusted remote device to generate random bits that can be certified to contain a certain amount of entropy. Certified randomness has many applications but is fundamentally impossible to achieve solely by classical computation. In this work, we demonstrate the generation of certifiably random bits using the 56-qubit Quantinuum H2-1 trapped-ion quantum computer accessed over the internet. Our protocol leverages the classical hardness of recent random circuit sampling demonstrations: a client generates quantum "challenge" circuits using a small randomness seed, sends them to an untrusted quantum server to execute, and verifies the server's results. We analyze the security of our protocol against a restricted class of realistic near-term adversaries. Using classical verification with measured combined sustained performance of $1.1\times10^{18}$ floating-point operations per second across multiple supercomputers, we certify $71,313$ bits of entropy under this restricted adversary and additional assumptions. Our results demonstrate a step towards the practical applicability of today's quantum computers.

DISCLAIMER

The protocol aims to certify uniformly random outputs independent of prior side information while expanding randomness, using an extractor and explicit operational safeguards. Its security analysis is proved for a restricted adversary under stated assumptions, and the paper notes those assumptions may be stronger than necessary.

  • The protocol seeks outputs that are unpredictable, uniformly distributed, and uncorrelated with client, server, and environmental side information.
  • Certified entropy is intended to exceed the randomness consumed to generate challenge circuits and select validation samples.
  • The client applies a randomness extractor to the received bitstrings and a private seed because the raw samples are not uniformly distributed.
  • Batches are discarded when they exceed the fixed cutoff, and the protocol aborts when average response time or XEB score fails its threshold.
  • Security is analyzed against an adversary mixing honest quantum samples with deterministic classical simulations under no postselection and single-use quantum-round assumptions.
  • The authors state that these adversarial assumptions are likely stronger than necessary and leave relaxed-assumption analysis for future work.

I. Motivation: Complexity-Theoretic Security

The security argument connects the LLHA conjecture to entropy generation in cross-entropy benchmarking, then extends the guarantee from repeated samples of one circuit to samples drawn across independently sampled circuits. The resulting MLXEB theorem provides complexity-theoretic justification for the protocol’s randomness-certification statistics.

  • Long-List Hardness Assumption: The LLHA conjecture is used to argue that devices achieving sufficiently high cross-entropy benchmark scores with sufficiently high probability must generate entropy.The conjecture is stated for long-list quantum-supremacy verification and supported by evidence in the random-oracle model.
  • Single-Circuit Entropy Guarantee: LXEBb,k requires distinct samples from one circuit whose cross-entropy score exceeds a threshold, preventing repeated high-probability outputs from artificially inflating the score.The associated theorem guarantees von Neumann entropy under LLHAB(D) for devices solving LXEBb,k with probability q.
  • Mixed Benchmarking Statistic: The main-text statistic differs from LXEBb,k by using one sample for each circuit in a set rather than multiple samples from a single circuit.This motivates defining mixed linear cross-entropy benchmarking, MLXEBb,k(D), for independently sampled circuits.
  • Mixed-Circuit Entropy Guarantee: The main result proves that solving MLXEBb,k(D) under LLHAB(D) ensures von Neumann entropy in the device’s classical output.The theorem applies to a set of k independently sampled circuits and outputs a classical state over k n-bit strings.
  • Protocol Relevance: This complexity-theoretic entropy guarantee justifies using the protocol’s XEB statistic for randomness certification and expansion.The paper subsequently uses “cross-entropy benchmarking score” for MLXEBb,k, with its primary XEB statistic matching the MLXEB definition up to normalization.

A. Proof of Theorem 6

The proof links low-entropy algorithms that pass LXEB or MLXEB to solving LLQSV, which would violate the assumed hardness of that problem. It uses heavy-hitter probabilities, expectation gaps, thresholding, and approximate counting to establish the reduction.

  • Theorem 6 reduction: A low-entropy algorithm that solves LXEB can be converted into a quantum-classical Arthur–Merlin protocol solving LLQSV.The reduction runs in time 2^B n^O(1) with O(n) bits of advice when ε = n^-O(1).
  • Technical correction: The analysis replaces a prior min-entropy condition with a von Neumann entropy bound because the former permits low-entropy strategies that still pass LXEB.The revised analysis also avoids an approximate-counting set defined from random samples that Arthur and Merlin could not consistently agree on.
  • Theorem 8 reduction: The MLXEB theorem establishes the analogous implication for the multi-circuit experiment used in the protocol.If such an algorithm exists, LLQSV_B(D) belongs to QCAMTIME(2^B n^O(1))/O(n).
  • Intermediate lemmas: The proof first shows that passing MLXEB forces the algorithm to output heavy hitters often enough to create a distinguishable expectation gap.Lemma 9 supplies the heavy-hitter probability condition, while later lemmas relate the resulting random variable to the yes- and no-cases of LLQSV.
  • Thresholding and counting: A threshold t converts the expectation gap into separated probabilities, enabling approximate counting to distinguish the two LLQSV cases.The threshold is obtained from Lemma 13 and applied through Corollary 14 to the variable Z_τ,t.

B. Multi-round Analysis

The single-round guarantees do not provide sufficiently strong soundness for the experiment, so a multi-round protocol is needed to accumulate entropy. The proposed modification sends multiple circuits per round, but its full analysis is not reproduced.

  • Need for multiple rounds: A multi-round protocol is therefore necessary, with entropy accumulation yielding smooth min-entropy linear in the number of rounds and qubits.The cited analysis uses a modified entropy accumulation theorem based on a single-round von Neumann entropy bound.
  • Modified protocol: The corresponding modification sends k circuits per round instead of one, but the multi-round analysis is not reproduced.The authors state that the same entropy-accumulation approach should apply using the single-round bound from Theorem 6.

C. Limitations of Asymptotic Guarantees

The asymptotic security results do not directly establish soundness for the finite experiment because of finite-size effects, unknown constants, and protocol mismatches. The experiment therefore uses a modified protocol analyzed against finite-sized adversaries.

  • Scope boundaries: Three issues limit applying Theorem 6 to the experiment: finite size, unknown constants in Eq. I.5, and differences between the analyzed and implemented protocols.These issues prevent direct use of the asymptotic result at experimental scale.
  • Scope boundaries: Theorem 6 applies asymptotically in n, so extending it to finite-sized experiments requires further analysis.The paper explicitly identifies this finite-size extension as unresolved within the presented analysis.
  • Assumptions: The complexity-theoretic analysis depends on LLHA_B(D), for which an upper bound B ≤ n/2 is known but no lower bound is available for any distribution D.This leaves the relevant hardness parameter incompletely bounded.
  • Scope boundaries: The asymptotic analysis guarantees single-round entropy for k output bitstrings, while extending entropy accumulation across rounds would require a substantially different protocol and costly probability estimation.Hundreds of circuits across hundreds of test rounds would make the required computations prohibitive.
  • Implemented protocol: The experiment instead uses four steps—circuit generation, client-server interaction, XEB verification, and randomness extraction—with classical validation of selected circuit-bitstring pairs.The protocol requests one sample per circuit and computes XEB over multiple circuits.
  • Adversary model: Security is established only for the prescribed restricted adversary model and its assumptions, not for adversaries using fundamentally different strategies.The paper specifically excludes deviations such as novel low-entropy algorithms on fault-tolerant quantum computers from the stated analysis.

1. Distribution of the XEB score of uniformly sampled bitstrings

For Haar-random quantum states, uniformly sampled bitstrings have exponentially distributed measurement probabilities. Summing probabilities over m samples gives an Erlang distribution and determines the uniform-sampling XEB-score distribution.

  • Probability model: A random n-qubit quantum state induces bitstring probabilities following the Porter–Thomas distribution.The state dimension is N = 2^n.
  • Uniform sampling: Uniformly sampling a bitstring produces a measurement probability with an exponential distribution, despite the bitstring itself being uniformly selected.The probability is p(x) = Tr(|x⟩⟨x|ρ) for a Haar-random state ρ.
  • Uniform sampling: The sum of m independent sampled probabilities follows an Erlang distribution with shape m and scale determined by N.This sum is the distributional basis for the uniform-sampling XEB calculation.
  • XEB distribution: The CDF of the uniform-sampling XEB score is expressed using the regularized lower-incomplete Gamma function.The paper gives Pr(XEB_m,U ≤ χ) = Γ̃(m, m·(χ + 1)).

2. Distribution of the XEB score of bitstrings perfectly sampled from the quantum state

Quantum sampling from a random state yields a probability distribution governed by the Porter–Thomas model, enabling an Erlang-based distribution for the XEB score.

  • Sampling bitstrings from a random quantum state produces probabilities distributed according to a size-normalized Porter–Thomas density.The resulting probability density is proportional to e^(-N·p(x))·p(x).
  • The sum of m independent sampled probabilities follows an Erlang distribution with shape parameter 2m.This distribution determines the cumulative distribution function of the XEB score.
  • The XEB cumulative distribution is expressed as the regularized incomplete gamma function evaluated at m·(χ + 1).The expression is Pr(XEB_m,Q ≤ χ) = Γ̃(2m, m·(χ + 1)).

3. Distribution of the XEB score of bitstrings sampled from a mixture

The XEB distribution extends from perfect quantum samples to mixtures of quantum and uniform samples, while finite fidelity is modeled through depolarizing noise.

  • For a verification set containing l quantum samples and m − l uniform samples, the total probability follows an Erlang distribution with shape m + l.This yields the XEB cumulative distribution Pr(XEB_m,l ≤ χ) = Γ̃(m + l, m·(χ + 1)).
  • Finite-fidelity sampling is modeled as a mixture of ideal quantum sampling with probability ϕ and uniform sampling with probability 1 − ϕ.The state is represented as ρ_ϕ = ϕ|ψ⟩⟨ψ| + (1 − ϕ)I/N.
  • The finite-fidelity XEB distribution combines the conditional XEB distribution for l Porter–Thomas samples with the binomial probability of obtaining l such samples.The resulting cumulative distribution is denoted XEB_m,ϕ.
  • The adversarial-server model includes a classical control unit, classical computer, and quantum computer, without assuming authenticated communication.The server model therefore includes parties with access to the client–server communication channel.

1. Circuit sampling and hardness assumptions

The security analysis relies on Porter–Thomas behavior and classical hardness for the chosen random circuits, then restricts adversaries to computational and sampling models that can be analyzed.

  • Circuit sampling and hardness assumptions: Random-circuit output probabilities are assumed to follow the Porter–Thomas distribution, and numerical evidence shows convergence toward it for the chosen circuit family.The evidence includes total-variation-distance behavior and Shannon-entropy statistics across circuit sizes.
  • Circuit sampling and hardness assumptions: High-XEB classical spoofing is assumed to be as hard as computing the output probabilities of the selected quantum circuits.Known asymptotic hardness results do not by themselves establish the difficulty of spoofing finite-sized experiments.
  • Circuit sampling and hardness assumptions: XEB can become unreliable as a fidelity indicator in some noise regimes, while the experiment is analyzed below the stated phase-transition point.For the reported parameters, the effective process infidelity per qubit per layer is approximately 1 − 0.99775 and ϵ·n ≈ 0.13.
  • Circuit sampling and hardness assumptions: A proposed classical spoofing algorithm can generate noisy-circuit-like samples, but its runtime scales as O(M 1/ε), making it impractical for realistic experiments.This limits its direct threat under the stated experimental setting rather than disproving the underlying asymptotic concern.
  • Assumptions on computing devices: The adversarial model bounds classical performance, assumes client-equivalent tensor-network methods, and restricts classical sampling to frugal rejection sampling.Additional classical capabilities can be represented by increasing the adversary’s computational power A.
  • Assumptions on computing devices: The analysis restricts the quantum computer and models partial tensor-network contraction as finite-fidelity sampling equivalent to sampling from a depolarized state.Numerical observations support the equivalence for the XEB analysis, but the probability distribution of postselected attacks remains unresolved.

D. Bounds on the Entropy Certified by the Protocol

The protocol bounds certified entropy by relating an adversary’s XEB-passing probability to the number of quantum samples it must execute. This yields a lower bound on smooth min-entropy for non-aborting executions.

  • A lower bound on conditional smooth min-entropy is sufficient to prove protocol soundness.
  • The analysis first bounds the probability that an adversary passes the XEB test after executing Q quantum rounds, then determines the minimum required Q.
  • At fixed M and m, protocol performance remains unchanged when A · Tthreshold/T is unchanged.
  • The bound decomposes the XEB-passing probability into events where the number of Porter–Thomas bitstrings exceeds or remains below Lmax, giving Pr[Ω] ≤ ε1 + ε2.
  • Lemma 2 bounds an adversary’s probability of passing the XEB test as εadv(Q, χ) = ε1 + ε2 for classical power A and Q quantum samples.
  • Qmin is selected from the adversarial bound and used to lower-bound the smooth min-entropy of the received samples conditioned on side information.

E. Proof of Protocol Soundness

Soundness follows by applying a quantum-proof strong extractor to the protocol’s smooth-min-entropy bound. The construction accounts for extractor seeds, initial randomness, aborts, and restrictions on seed reuse.

  • The soundness proof compares the real extracted output with an ideal maximally mixed output conditioned on the protocol’s state and side information.
  • The extractor acts on the M output registers using a private client-held seed, and its output length depends on input entropy, extraction error, and seed length.
  • The protocol uses a quantum-proof strong extractor to convert the entropy bound into εsou-soundness.
  • Two-universal hashing and Trevisan extraction provide alternative soundness constructions with different seed and output-length requirements.
  • The protocol’s certified randomness expansion accounts for expected output bits, extractor-seed consumption, and randomness used to generate circuits and select test rounds.
  • The extractor seed generally cannot be reused because the public input and deterministic output can reveal the seed.

3. Simulation algorithm in our experiment

The experiment estimates random-circuit simulation costs with tensor-network contractions optimized for GPU time-to-solution. It searches contraction orders and slicing choices across hardware-specific settings.

  • CoTenGra determines contraction schemes, using KaHyPar for contraction-order optimization and slicing with subtree reconfiguration and simulated annealing.
  • Efficiency is the ratio of theoretical contraction time to actual GPU contraction time.
  • Approximately 750k contraction schemes are evaluated, and each GPU uses the scheme with the lowest measured time-to-solution.
  • For depth-10 circuits on NVIDIA-V100, contraction efficiency and time are evaluated as functions of α, with α = 128 selected for Summit.

4. Heterogeneous high-performance computing platforms of our experiment

Verification uses four U.S. Department of Energy supercomputers with differing architectures and performance characteristics. The experiment therefore evaluates practical time-to-solution rather than relying only on theoretical FLOP peaks.

  • Quantum-circuit verification uses Frontier, Summit, Perlmutter, and Polaris supercomputers.
  • Actual time-to-solution depends on memory bandwidth, device architecture, caching, and reduced- or mixed-precision support in addition to theoretical peak performance.
  • The experiment converts heterogeneous supercomputing resources into Frontier node-hours to represent the verification budget.
  • The reported computational budget does not equal exactly 2.8×10^23 floating-point operations because efficiencies and FLOP counts vary across machines and contraction schemes.
  • Table II reports single-precision theoretical peak performance for the four supercomputers, derived from GPU counts and single-GPU performance.

B. Selection of Experimental Parameters

The experiment selects challenge circuits and verification parameters to balance classical simulation hardness, quantum execution fidelity, statistical uncertainty, and available verification resources.

  • Parameter selection: The protocol requires circuits difficult enough to resist fast classical simulation but easy enough for client-side supercomputer verification.This trade-off makes circuit difficulty inversely proportional to the number of circuits that can be verified within the available budget.
  • Verification design: The protocol optimizes the number of verification circuits because adversarial simulation hardness favors smaller m, whereas statistical stability favors larger m.With the available fixed verification budget, the experiment verified m = 1,522 circuits.
  • Circuit construction: The challenge family uses random n-qubit circuits with UZZ(π/2) entangling gates, random SU(2) single-qubit layers, and edge-colored graph topologies.The topology determines entangling pairings across circuit layers, while the single-qubit gates are randomized using secret seeds.
  • Circuit construction: Topology selection estimates tensor-network contraction costs and excludes circuits that are obviously too expensive or too cheap to simulate.The remaining candidates are evaluated using expected GPU execution times and contraction schemes optimized across classical computing systems.
  • Data collection: The experiment submitted 60,952 circuits in 1,993 batches and received 30,010 valid samples.The per-circuit quantum-computer time is calculated from each batch’s recorded interval divided by its batch size.

F. Randomness Extraction

The extraction stage converts certified entropy in the experimental samples into output bits expected to be close to uniform using a quantum-proof strong extractor.

  • Experimental parameters: The experiment uses n = 56, M = 30010, T_tot = 64641 seconds, XEB_test = 0.32, and m = 1522.The protocol passes with abortion thresholds χ = 0.30 and t_threshold = 2.2 s.
  • Certified entropy: At ε_sou = 10^-6 and A = 4×Frontier, the certified smooth min-entropy rate is h = 0.04.The rate is defined as the certified smooth min-entropy divided by M·n.
  • Randomness extraction: The raw 56·M bits are processed by a seeded Toeplitz extractor to obtain output bits expected to be close to uniform.The Toeplitz extractor is described as a quantum-proof strong extractor.

V. Details on Outlook for Future Experiments

The outlook analyzes how fidelity, sampling time, verification budget, and adversary power affect certified entropy and security while retaining an optimized verification count.

  • Parameter outlook: The analysis examines how improving quantum fidelity, reducing average sample time, increasing verification budget, or reducing adversary power changes protocol performance.The performance measures include resulting smooth min-entropy and achievable security parameters.
  • Scaling regime: For economic viability, the protocol targets a very small verified-sample fraction, m/M ≪ 1.The analysis considers the limit of infinite M with finite m to lower-bound the quantum-sample fraction.
  • Asymptotic model: In the infinite-M, finite-m limit, the Porter–Thomas fraction becomes R = R_Q + (1 − R_Q)·⟨ϕ_A⟩.The verification-set count of Porter–Thomas bitstrings then follows a binomial distribution.
  • Asymptotic model: The resulting verification-set distribution matches the cumulative distribution function for a finite-fidelity honest server with fidelity R.This identifies the asymptotic model with the finite-fidelity honest-server CDF.
Loading 2503.20498v1…