In recent years, numerous theoretical results have shown evidence that quantum computers have the potential to tackle a wide range of problems out of reach of classical techniques. The main examples include factoring large integers⁶, implicitly solving exponentially sized systems of linear equations⁷, optimizing intractable problems⁸, learning certain functions⁹ and simulating large quantum many-body systems¹⁰. However, accounting for considerations such as quantum error correction overheads and gate speeds, the resource requirements of known quantum algorithms for these problems put them far outside the reach of near-term quantum devices, including many suggested fault-tolerant architectures. Consequently, it is unclear whether the devices available in the near term can benefit a practical application¹¹.

Starting with one of the first ‘quantum supremacy’ demonstrations⁵, several groups have used random circuit sampling (RCS) as an example of a task that can be executed faster and with a lower energy cost on present-day quantum computers compared with what is achievable classically^4,12,13,14. Yet, despite rapid experimental progress, a beyond-classical demonstration of a practically useful task performed by gate-based quantum computers has so far remained unknown.

Random number generation is a natural task for the beyond-classical demonstration because randomness is intrinsic to quantum mechanics, and it is important in many applications, ranging from information security to ensuring the fairness of processes such as jury selection^15,16,17. The main challenge for any client receiving randomness from a third-party provider, such as a hardware security module, is to verify that the bits received are truly random and freshly generated. Although certified randomness is not necessary for every use of random numbers, the freshness requirement is especially important in applications such as lotteries and e-games, in which several parties (which may or may not trust each other) need to ensure that a publicly distributed random number was generated on demand. Moreover, certified randomness can be used to verify the position of a dishonest party^18,19,20.

Protocols exist for certifying random numbers based on the violation of Bell inequalities^{15,21,22,23,24}. However, these protocols typically require the underlying Bell test to be loophole-free, which can be hard for the client to enforce when the quantum devices are controlled by a third-party provider. This approach thus necessitates that the client trust a third-party quantum device provider to perform the Bell test faithfully.

Alternatively, ref. ³ proposed a certified randomness protocol that combines RCS with ‘verification’ on classical supercomputers^3,25. This type of protocol allows a classical client to verify randomness using only remote access to an untrusted quantum server. A classical client pseudorandomly generates n-qubit challenge circuits and sends them to a quantum server, which is asked to return length-n bitstrings sampled from the output distribution of these circuits within a short amount of time (Fig. 1a,c). The circuits are chosen such that no realistic adversarial server can classically simulate them within the short response time. A small subset of circuits is then used to compute the cross-entropy benchmarking (XEB) score²⁶ (Fig. 1b), which reflects how well the samples returned by the server match the ideal output distributions of the submitted circuits. Extensive complexity-theoretic evidence suggests that XEB is hard to ‘spoof’ classically^27,28. Therefore, a high XEB score, combined with a short response time, allows the client to certify that the server must have used a quantum computer to generate its responses, thereby guaranteeing a certain amount of entropy with high probability. Our analysis quantifies the minimum amount of entropy that an untrusted server, possibly acting as an adversary, must provide to achieve a given XEB score in a short amount of time.

a, The idealized protocol. A client submits M random circuits \(\C_i\_i\in [M]\) serially to a randomness server and expects bitstrings \(\x_i\_i\in [M]\) back, each within a time t_QC. b, A subset of circuit-bitstring pairs is used to compute the XEB score. The XEB score has distributions (bottom plot for qualitative illustration only) corresponding to either an honest server or an adversarial server performing a low-fidelity classical simulation. For any XEB target indicated by the dashed line, an honest server may fail to achieve a score above this threshold with a probability P_fail. c, Illustration of the challenge circuits, consisting of layers of U_ZZ gates sandwiched between layers of random SU(2) gates on all qubits. The arrangement of two-qubit gates is obtained via edge colouring (right) on a random n-node graph. d, Client-server interaction as implemented in our protocol. Following a device-readiness check (‘precheck’), the client submits a batch of 2b circuits and expects all the samples corresponding to the batch to be returned within a cutoff duration T_b,cutoff. Note that only one batch with execution time T_batch is illustrated in the figure. The client continues the protocol until M total circuits have been successfully executed.

The protocol proposed in ref. ³ provides a complexity-theoretic guarantee of Ω(n) bits of entropy for a server returning many samples from the same circuit. This protocol is best suited for quantum computing architectures with overheads that make it preferable to sample a circuit many times after loading it once. In practice, the classical simulation cost of sampling a circuit many times is comparable to the cost of sampling only once²⁹. Furthermore, the trapped-ion-based quantum computer used in this work is configured to feature minimal overhead per circuit, such that executing many single-shot circuits does not introduce a substantial time penalty per circuit compared with sampling one circuit many times. Together, these two observations motivate strengthening the security of the protocol by requesting the server to return only one sample per circuit. To this end, in Supplementary Information section I, we extend the complexity-theoretic analysis to this modified setting of one sample per circuit, guaranteeing Ω(n) bits of entropy.

In this work, we report an experimental demonstration of an RCS-based certified randomness protocol. Our main contributions are as follows. First, inspired by ref. ³, we propose a modified RCS-based certified randomness protocol that is tailored to near-term quantum servers. Second, we prove the security of our implementation against a class of realistic finite-sized adversaries. Third, we use a high-fidelity quantum computer and exascale classical computation to experimentally realize this proposed protocol, pushing the boundaries of both quantum and classical computing abilities. By combining the high-fidelity Quantinuum H2-1 quantum processor with exascale verification, we demonstrate a useful beyond-classical application of gate-based digital quantum computers.

In our proposed protocol, shown in Fig. 1d and detailed in the Methods, the client pseudorandomly generates a sufficiently large number of n-qubit quantum circuits and then sends them in batches of 2b circuits, where b is an integer. After a batch is submitted, the client waits for 2b length-n bitstrings to be returned within T_b,cutoff seconds. The batch cutoff time prevents the protocol from stalling and is fixed in advance based on preliminary experiments to a value intended to maximize the amount of certifiable entropy while ensuring that the average response time per circuit remains low enough to preclude classical simulation as a viable strategy for the server to generate responses. If a batch times out or if a failure status is reported, all of the outstanding jobs in the batch are cancelled, and all bitstrings received from the batch are discarded. Consequently, results from a failed batch are not included in calculating the XEB score or entropy extraction. Batches are continually submitted until M valid samples are collected. The cumulative response time for successful batches gives the total time T_tot and the average time per sample t_QC = T_tot/M. Subsequently, the client calculates the XEB score on a subset of size m randomly sampled from the M circuit–sample pairs:

where \(\mathcalV\) is the set of indices for the random subset of size m and P_C(x) = |⟨x|C|0⟩|² is the probability of measuring bitstring x from an ideal quantum computer executing circuit C. If the bitstrings x_i are perfectly drawn from the output distributions of sufficiently deep random circuits C_i, the XEB score is expected to concentrate around 1. By contrast, if the x_i are drawn from distributions uncorrelated with the distributions induced by C_i, the XEB score is expected to concentrate around 0. The client decides to accept the received samples as random bits based on two criteria. First, the average time per sample must be lower than a threshold t_threshold, which is chosen to preclude high-fidelity classical simulation. This time can be lower than T_b,cutoff because it is advantageous from the perspective of extractable entropy to accept some samples with response time slightly larger than t_threshold as long as the average response time remains low. Second, the XEB score on \(\mathcalV\) must be greater than a threshold χ ∈ [0, 1]. All of t_threshold, χ and T_b,cutoff are determined in advance of protocol execution, based on (for example) preliminary hardware experiments, with the goal of certifying a certain fixed amount of entropy at the end of the protocol with high probability. Together, the protocol succeeds if

and otherwise aborts.

The security of our protocol relies on the central assumption that, for the family of pseudorandom circuits we consider, there exists no practical classical algorithm that can spoof the XEB test used in the protocol. We analyse the protocol security by modelling a restricted but realistic adversarial server that we believe to be the most relevant: for each circuit received, the adversary either samples an output honestly from a quantum computer or performs classical simulation (Fig. 2a). As only the former contains entropy, the adversary tries to achieve the threshold XEB score with the fewest quantum samples, to pass the XEB test while returning as little entropy as possible. For our protocol, we assume an adversary with a perfect-fidelity quantum computer, which allows the adversary to spoof the maximum number of bitstrings classically. We further assume that the classical computational power of the adversary is bounded by a fixed number of floating-point operations per second (FLOPS) \(\mathcalA\), which may be measured relative to the most powerful supercomputer in the world (at the time of experiment, the Frontier supercomputer; see https://www.top500.org/lists/top500/2024/06/), and that the adversary possesses the same optimized methods to simulate the circuits as the client has. Note that an adversary possessing more powerful classical methods for simulating circuits than expected can equivalently be modelled as an adversary with identical classical methods and larger computational power. We note that as the adversaries we analyse are allowed only a restricted set of strategies, the subsequent mathematical results hold only in this limited setting, conditioned on some additional assumptions further detailed in Supplementary Information section IIIC. To the best of our knowledge, the restricted set of classical and quantum adversary strategies considered here correspond to the current state of the art. We leave the incorporation of a broader class of adversaries to future analysis.

a, In the adversarial model considered in this work, Q samples are obtained using a perfect-fidelity quantum computer and M − Q using classical simulation. b, Probability of an honest server with fidelity ϕ = 0.3 failing to certify Q_min quantum samples (and corresponding threshold χ) with soundness ε_sou against an adversary four times more powerful than Frontier over repeated experiments, with the protocol parameters set to those from Table 1. c, Distribution of batch times per successful sample, from a total of 984 successful batches, in our experiment. The vertical dashed line indicates the average time per sample.

The client needs to ensure that the circuits are difficult to simulate within the time t_threshold. Otherwise, the server can use its classical supercomputer to deterministically simulate the circuits with high fidelity and generate samples that readily pass the tests in equation (2). For the family and size of circuits we consider, tensor network contraction is the most performant known method for finite-fidelity and exact simulation⁴ as well as sampling. If a circuit has a verification (exact simulation) cost of \(\mathcalB\) FLOPS, the adversary can simulate each circuit to a target fidelity of \(\mathcalA\cdot t_\rmthreshold/\mathcalB\) using partial contraction of tensor networks, for which the simulation cost and simulation fidelity are related linearly³⁰. The protocol is successful only if the parameters are chosen such that the fidelity ϕ of an honest server satisfies

This condition requires that there exists a gap between the fidelity of an honest server and that achievable by an adversary performing mostly classical simulations. If this condition is satisfied, the XEB score of an honest server will have a probability distribution with a higher average value than the probability distribution of the XEB of the adversary (qualitatively shown in Fig. 1b), allowing the client to distinguish between the two.

After certification (that is, if the tests in equation (2) pass), the client uses a randomness extractor to process the M samples. An ideal protocol for certified randomness either aborts, resulting in an ‘abort state’, or succeeds, resulting in a uniformly distributed bitstring that is uncorrelated with any side information. Viewing the protocol as a channel acting on some initial state composed of both the server and the client, an end-to-end protocol is said to be ε_sou-sound if, for any initial state, the end result is ε_sou-close (in terms of trace distance) to the ideal output: a mixture of the abort state and the maximally mixed state (see Supplementary Information section IIIA for the rigorous definition of soundness).

The entropy that the client can extract out of the received samples on successful execution of the protocol depends on how stringent its thresholds on the response time (t_threshold) and the XEB score (χ) are. It is in the interest of the client to set these thresholds as stringently as possible, to force the hypothetical adversary to draw more samples from the quantum computer, while still allowing that an honest server can succeed with high probability. As the thresholds are known to both parties, the strategy of the adversary is to minimize the use of the quantum computer while ensuring that the protocol does not abort. Based on the protocol thresholds, the client can determine the number of quantum samples Q_min such that the protocol aborts with a large probability 1 − ε_accept if the adversary returns fewer than Q_min samples from the quantum computer (see Supplementary Information section IVF for details). This lower bound on Q_min can be used to derive the minimum smooth min-entropy of the received samples. Note that the smooth min-entropy of an information source characterizes the number of random bits that can be extracted from the source. In particular, we devise an ε_sou-sound protocol that provides a lower bound on the smooth min-entropy \(H_\min ^\varepsilon _\rms\) (defined in Supplementary Information section IIID) with smoothness parameter ε_s = ε_sou/4 and with ε_accept = ε_sou. The results in the paper are reported in terms of the soundness parameter ε_sou and the smooth min-entropy \(H_\min ^\varepsilon _\rms\).

A smaller ε_sou makes a stronger security guarantee by making it more difficult for an adversary to pass the XEB test with a small Q_min. This may be achieved by choosing a higher threshold χ. However, a higher threshold also makes it more likely for an honest server to fail the XEB test, meaning that the honest server cannot be certified to have produced the target amount of extractable entropy. Note that this does not necessarily mean that the samples provided by the honest server do not contain entropy, only that they fail to satisfy the criteria of equation (2) and consequently the protocol aborts. In practice, it is desirable to ensure that an honest server fails only with a low failure probability P_fail. To that end, we may compute a threshold χ(P_fail) corresponding to any acceptable P_fail. This threshold, along with t_threshold, then allows us to determine Q_min for a target soundness ε_sou (Supplementary Information section IIID). Figure 2b shows the achievable Q_min at different P_fail and ε_sou, showing the trade-off between the three quantities at the fixed experimental configuration and the classical computational power of adversary (\(\phi ,t_\rmQC,M,m,\mathcalB\) and \(\mathcalA\)).

We demonstrate our protocol using the Quantinuum H2-1 trapped-ion quantum processor accessed remotely over the Internet. The experimental parameters are provided in Table 1. The challenge circuits (shown in Fig. 1c, see Supplementary Information section IVC for the considerations involved in choosing the circuits) have a fixed arrangement of 10 layers of entangling U_ZZ gates, each sandwiched between layers of pseudorandomly generated SU(2) gates on all qubits. The arrangement of two-qubit gates is obtained by edge colouring on a random n-node graph. Preliminary mirror-benchmarking experiments, along with gate-counting arguments based on the measured fidelities of component operations, enable us to estimate the fidelity of an honest server⁴. At the time of the experiment, the H2-1 quantum processor was expected to attain a fidelity of ϕ ≳ 0.3 or better on depth-10 circuits (multiple improvements were made to the H2-1 device after the collection of the data of this experiment that slightly increased the fidelity estimate in ref. ⁴). Likewise, the same preliminary experiments also let us anticipate average time per sample to be approximately 2.1 s, with a long-tailed timing distribution out to just below 2.5 s, as also seen in the full experiment in Fig. 2c. Reasonable (P_fail = 50%) protocol success rates can therefore be achieved with thresholds t_threshold = 2.2 s and χ = 0.3. For illustrative purposes, we describe the experiment based on these choices (in practice, one might want to lower P_fail by setting χ somewhat below the expected value). The batch cutoff time is set to be T_b,cutoff = (2b) × 2.5 s, anticipating that the relatively small expected fraction of batches taking average time per sample between t_threshold = 2.2 s and 2.5 s would contribute additional entropy to the received samples while being unlikely to increase the average time per sample from the expected 2.1 s past the threshold of 2.2 s.

The circuit family considered has a simulation cost of \(\mathcalB=90\times 1^18\) FLOPS on the Frontier supercomputer of the Department of Energy³¹, the most powerful supercomputer in the world, to our knowledge, at the time of writing (https://www.top500.org/lists/top500/2024/06/). Following a detailed estimate of runtime on Frontier, we determine an exact simulation time of 100.3 s per circuit when using the entire supercomputer at a numerical efficiency of 45%, where numerical efficiency is the ratio between the actual algorithm runtime and its theoretical expectation (see Supplementary Information section IVA for details on the circuit simulation cost).

In our experiment, we use two batch sizes, b = 15 and b = 20; most of the batches have b = 15. In total, we submitted 1,993 batches for a total of 60,952 circuits. From those, we obtain a total of M = 30,010 valid samples out of 984 successful batches. The cumulative device time of the successful samples was 64,652 s, giving an average time of t_QC = 2.154 s per sample, inclusive of all overheads such as communication time. Figure 2c shows the distribution of t_QC per successful sample.

In this work, the classical computational budget of the client is spread across the Frontier³¹, Summit³², Perlmutter³³ and Polaris³⁴ supercomputers equipped with graphics processing units (GPUs), which are especially suitable for quantum circuit simulations. Of the four supercomputers, Frontier and Summit were used at full-machine scale during verification. We measure the sustained peak performance of 897 petaFLOPS and 228 petaFLOPS, respectively (corresponding to numerical efficiencies of 45% and 59%), achieving a combined performance of 1.1 exaFLOPS (see Supplementary Information section IVE). We compute the XEB score for m = 1,522 circuit–sample pairs, obtaining XEB_test = 0.32. The complete set of experimental parameters is listed in Table 1.

The measured fidelity of XEB_test = 0.32 and measured time per sample t_QC = 2.154 s pass the protocol specified by χ = 0.3 and t_threshold = 2.2 s. For a choice of soundness parameter ε_sou and a smoothness parameter ε_s = ε_sou/4, the protocol thresholds determine the number of quantum samples Q and the smooth min-entropy \(H_\min ^\varepsilon _\rms\) guaranteed by the success of this protocol against an adversary with classical resources bounded by \(\mathcalA\). In Table 2, we report the smooth min-entropy rate, \(H_\min ^\varepsilon _\rms/(56\times M)\), for a range of \(\mathcalA\) and ε_sou (see Supplementary Information section IVF for details of this calculation). This is to show that if we want to increase the security of the protocol either by increasing the assumed classical computational power of the adversary or by reducing the soundness parameter, the amount of entropy that we can obtain must reduce. In particular, we highlight that at ε_sou = 10⁻⁶, we have Q_min = 1,297, corresponding to \(H_\min ^\varepsilon _\rms=\mathrm71,313\) against an adversary four times more powerful than Frontier (under the assumptions discussed earlier).

We feed the 56 × 30,010 raw bits into a Toeplitz randomness extractor³⁵ and extract 71,273 bits (see Supplementary Information section IVF for details on extraction and the determination of extractable entropy). We note that the Toeplitz extractor is a ‘strong’ seeded extractor for which the output is independent of the seed. For private use of the randomness, in which the extracted bits are not shown, the extractor seed can be reused. We append the seed used in the extractor to the protocol output and do not count the seed as randomness ‘consumed’ by our protocol. The total input randomness used to seed the pseudorandom generator is thereby only 32 bits, and our protocol achieves certified randomness expansion. We further note that other extractors can be used that may consume less seed but have different security guarantees.

Future experiments are expected to improve device fidelity (higher ϕ) and execution speed (lower t_QC). Adjusting protocol thresholds (χ and t_threshold) against improved device specifications stands to improve our protocol in terms of the achievable entropy, the adversarial computational power that can be guarded against and the soundness parameter. Figure 3 shows these metrics as we improve t_QC and ϕ (see Supplementary Information section V for details of this calculation). Conversely, for a fixed adversary and soundness parameter, any improvement in t_QC and ϕ reduces the verification budget required to certify a target number of quantum samples Q, making our protocol more cost-effective. Any improvement in entropy, all else being equal, translates into a higher throughput in the sense of a higher rate of entropy generation per second. With χ = 0.3 and t_threshold = 2.2 s, our experiment has a bitrate of 71,273/(30,010 × 2.2 s) ≈ 1 bit per second at ε_sou = 10⁻⁶. For ε_sou = 10⁻⁶ and P_fail = 0.1, improving fidelity to ϕ = 0.67 and response time to t_QC = 0.55 s would let us achieve the bitrate of the NIST Public Randomness beacon³⁶ (512 bits per minute). We note that improvement in t_QC can come from higher clock rates as well as parallelization over multiple quantum processors or over many qubits of one large quantum processor.

Improvement in metrics as fidelity ϕ and time per sample t_QC improve. All panels assume the same verification budget as this experiment, classical simulation numerical efficiency of 50% for both verification and spoofing, and target failure probability P_fail = 10⁻⁴. a, Smooth min-entropy rate, \(h=H_\min ^\varepsilon _\rms/(M\cdot n)\), against an adversary four times as powerful as Frontier with ε_sou = 10⁻⁶ and ε_s = ε_sou/4. b, Adversarial power that still allows h = 0.01 to be guaranteed with ε_sou = 10⁻⁶. c, Soundness parameter ε_sou that still allows h = 0.01 to be guaranteed with an adversary that is four times as powerful as Frontier.

The security of our protocol relies on the circuits being difficult to simulate. When better exact simulation techniques are developed by researchers in the future, both the adversary and the client can use the improved techniques to spoof and verify: these symmetric gains neutralize each other. Although a notable improvement in approximate simulation techniques may benefit spoofing asymmetrically, the client might be able to neutralize those gains by modifying the ensemble of challenge circuits to make approximate simulations more difficult.

In summary, this work implements a protocol for certified randomness, which also lends itself to multiparty and public verification. We note that the bit rate and soundness parameter achieved by our experiment, the restricted adversarial model, as well as the numerous assumptions used in our analysis limit the immediate deployment of the proposed protocol in production applications. However, we numerically analyse how future developments may improve the security and cost-effectiveness of our protocol. Our experiments pave the way for new opportunities in cryptography and communication.