Robust randomness generation on quantum processing units

Random numbers are a ubiquitous resource in computation and cryptography. For example, in security, random numbers are crucial to creating keys for encryption. Quantum random number generators (QRNGs), that make use of the inherent unpredictability in quantum physics, promise enhanced security compared to standard cryptographic pseudo-random number generators (CPRNGs) based on classical technologies.

In this notebook, we implement our own QRNG. Namely, we program two separate quantum processor units (QPUs) from different suppliers in Amazon Braket to supply two streams of weakly random bits. We then show how to generate physically secure randomness from these two weak sources by means of classical post-processing based on randomness extractors. The prerequisites for the tutorial are a basic understanding of quantum states, quantum measurements, and quantum channels. For a detailed explanation of these concepts we refer to the Amazon Braket notebook Simulating noise on Amazon Braket.

We believe that randomness generation is a practical application of nowadays available noisy and intermediate scale quantum (NISQ) technologies.

Table of contents

• Amazon Braket
• Quantum circuit for randomness generation
• Quick implementation
• Critical assessment
• Interlude randomness extractors
  • Quantum information
• Extractor construction
  • Example
  • Implementation
• Unpredictability of physical sources
  • Noise as leakage
  • Numerical evaluation
• Putting everything together
• Beyond current implementation
• Literature

Amazon Braket

We start out with some general Amazon Braket imports, as well as some mathemtical tools needed.

Quantum circuit for randomness generation

Arguably the simplest way of generating a random bit on a quantum computer is as follows:

• Prepare the basis state vector
• Apply the Hadamard gate leading to the state vector
• Measure in the computational basis .

By the laws of quantum physics, the pre-measurement probability distribution is then the uniformly distributed and leads to one random bit .

In the following, we discuss how above protocol is conceptually different from randomness obtained from classical sources and show in detail how it is implemented reliable even when the underlying quantum processing units employed are noisy. By the end of this tutorial, you will be able to create your own random bits from the quantum processing units available on Amazon Braket.

Quick implementation

The Hadmard gate based quantum circuit for generating one random bit can be repeated or run in parallel times, leading to a random bit string of length . The corresponding circuit is easily implemented in Amazon Braket:

Let us run this Hadamard circuit with qubits in the local quantum simulator for shots:

(Note: We will work on actual QPUs towards the end of this tutorial.)

Critical assessment

The advantage of such quantum random number generators over implementations based on classical technologies is that the outcomes are intrinsically random. That is, according to the laws of quantum physics, the outcome of the measurement is not only hard to predict, but rather impossible to know before the measurement has taken place.

However, since current quantum processing units are noisy to a certain degree, there are at least three potential problems that need to be addressed:

• First, the noise acting on all states and operations performed might lead to a systematic bias towards the probability of getting the measurement outcomes or , respectively.
• Second, even if aforementioned noise is not biased towards certain measurement outcomes, the generated randomness is no longer solely based on intrinsically random quantum effects, but rather partly on the noise present.
• Third, whereas by the laws of quantum physics a pure quantum state cannot be correlated to the outside world, any noisy acting on the system corresponds to information leaking to the environment. This is because no information is destroyed in quantum physics and hence, a malicious third party knowing about the noise occurring will be able to guess the generated bits (at least up to a certain degree).

When the noise model acting on the quantum processor units is characterized to some degree (e.g., by means of previous benchmarking), these shortcomings can be overcome by employing two independent quantum processor units, together with an appropriate classical post-processing. The latter is based on classical algorithms from the theory of pseudo-randomness, so-called two-source extractors. This is what we discuss next.

In the following, we refer a few times to the theory paper [1] that features formal cryptographic security definitions, together with mathematical proofs, as well as some statistical methods tailored to intermediate scale quantum devices. These pointers can be safely ignored when only interested in the implementation of our QRNG.

Interlude randomness extractors

Two-source extractors allow distillation of physically secure random bits from two independent weak sources of randomness whenever they are sufficiently unpredictable to start with. The relevant measure of unpredictability is thereby given by the min-entropy of the respective sources, defined for the probability distribution as

That is, the min-entropy exactly quantifies how well we can guess the value of the source, or in other words, how unpredictable the source is. For example, for -bit distributions we have , where corresponds to a deterministic distribution containing no randomness and to the perfectly random, uniform distribution.

A two-source extractor is a function such that for any two independent sources with min-entropy at least and , respectively, the output of length is close in variational distance to the perfectly random, uniform distribution of size :

So, two inpedendent sources that are only weakly random get condensed by these algorithms to one output that is (nearly) perfectly random! Importantly, the output becomes truly physically random with no computational assumptions introduced.

Quantum information

For our setting we need an extension of this concept, as a potentially malicious third party can collect quantum information about the weak source of randomness . The corresponding conditional min-entropy is defined as

where denotes the maximal probability allowed by quantum physics to guess the classical value by applying any measurements on the quantum information . We notice that even though does not have a closed form expression, it is efficiently computed by means of a semidefinite program (see the theory notes [1] for details). This is also how we will evaluate the conditional min-entropy quantity later on.

Accordingly, a quantum-proof two-source extractor is then function such that for any two independent sources with quantum conditional min-entropy at least and , respectively, we have for in quantum variational distance

where denotes the fully mixed qubit state. That is, the extractor should not only make the output bits perfectly random, but also decouple them from any outside correlations initially present - up to the security parameter .

For more details about these concepts, we refer to the theory notes [1] and references therein. All that is important to us here, is that there exist quantum-proof two-source extractors with good parameters. Next, we discuss one particular such construction that we subsequently implement in an efficient manner.

Extractor construction

In this paragraph, we provide an explicit construction of a quantum-proof two-source extractor that efficiently provides non-zero output for a wide range of sizes of the inputs and . Namely, we employ a Toeplitz matrices based construction originally discussed in [2]:

For the security parameter and inputs of size and , respectively, the function defined below is a quantum-proof two-source randomness extractor with output size

The function is explicitly given via the vector-matrix multiplication

featuring the Toeplitz matrix

The quantum-proof property of this construction, as well as its complexity, is explicitly disccused in the theory notes [1].

For our setting, we will have sources with linear min-entropy rates for . The Toeplitz construction then works whenever and we can compute the required input size for fixed output size as

A simple example shows that these numbers work well in practice, even for very small input sizes around .

Example

Let us set the security parameter to , say that we have min-entropy sources with linear rates and , and ask for fully random bits. According to the formulae above, together with weakly random bits can be condensed into fully random bits (up to the security parameter ).

Next, we give an efficient implementation of this Toeplitz based construction.

Implementation

The vector-matrix multiplication a priori has asymptotic complexity in big O-notation, which is prohibitive for larger input sizes . However, we discuss in the theory notes [1] that the operation is actually implemented in asymptotic complexity by first embedding the problem into circulant matrices and then making use of the Fast Fourier Transform (FFT). The corresponding code then performs well up to input sizes . The following example demonstrates this implementation:

As an alternative, we note that efficient implementations of other quantum-proof two-source extractors are discussed in [3].

Unpredictability of physical sources

Given above methods on randomness extraction, the next step is to give lower bounds on the min-entropy present in the output distributions generated from our -fold Hadamard circuit. For that, we need to model the noise present in the quantum processing units.

Generally, for any given quantum processing unit, the supplier typically publishes some type of noise specification with it. This includes both, the noise characterization of state preparation, as well as the read-out measurements. In case such specifications are not available, or if one wants to double check them, it is in principle possible to benchmark the device. We refer to the theory notes [1] for more details on this and just mention here that we do not need a full characterization of the device, but rather only conservative upper bounds on the noise strength. This then translates into lower bounds on the min-entropy present in the system.

For our case, since we are only applying single qubit gates for our Hadamard circuit, the noise is captured well by single qubit noise models. Moreover, for the state preparation step via Hadamard gates, the typical noise in quantum architectures is uniform, depolarizing noise of some strength . That is, all possible single qubit errors such as bit flip or phase flip errors are equally likely, leading to the effective evolution

mapping any input qubit state onto a linear combination of itself and the maximally mixed qubit state . Note that we now work with general mixed states in order to model classical statistical uncertainty coming from the noise model.

So effectively, before the measurement step, instead of the perfect pure state as defined by the vector , we have the mixed state

at hand.

Next, we note that instead of the ideal measurement device given by , the typical noisy measurement device is described by

with some bias towards reading-out the ground state over . The post-measurement probability distribution is then given as

instead of the perfectly uniform distribution . Note that the former distribution has non-maximal min-entropy

More generally, as measurement devices are the most sensitive element of quantum randomness generation, we discuss in the theory notes [1] methods for benchmarking them (even when only noisy state preparation is available).

Noise as leakage

It is, however, crucial to realize that is not yet the quantity relevant for secure quantum randomness generation. As information is never lost in quantum mechanics, all the noise carries information to the environment, where it can in principle be picked up by an attacker. That is, we need to estimate the conditional min-entropy of the post-measurement probability distribution given any complementary information that leaked into the environment [5].

This is worked out in detail in the theory notes [1] by means of so-called purifications of both, the noisy qubit state , as well as the noisy measurement device , leading to the additional qubit registers and , respectively. The relevant so-called classical-quantum state to consider then takes the form

with a classing part and the quantum parts depending on both noise parameters . The corresponding conditional min-entropy is

with the gap between the conditional and the unconditional term typically being strict.

We reiterate that the reason for mathematically introducing the purification registers and working with the conditional min-entropy, is to make sure that the output bits generated are random even conditioned on the knowledge of the noise. This ensures that the randomness created is from a purely quantum origin and is secure against any eavesdropping from a malicious third party.

We mention that a more detailed discussion of this point is given in the work [5].

Numerical evaluation

In the following, we use the noise parameters and for the quantum processing units and this immediately gives

The next step is to numerically evaluate the conditional min-entropy

This is done by means of a standard semidefinite program (sdp) solver as follows:

That is, for the chosen noise parameters and we find

By varying the noise parameter to other values, one also sees by inspection that the conditional min-entropy is monotone in both and . Importantly, this ensures that the outputted randomness will be safe to use whenever we put a conservative estimate on the noisy strength, even in the absence of an exact characterization of the underlying quantum processing units.

Finally, whenever we run our Hadamard circuit times or on qubits in parallel, the overall conditional min-entropy is just given by

This reason is that we only consider single qubit product noise together with the min-entropy being additive on product states. This then leads to the promised linear min-entropy rates for going into the Toeplitz two-source extractor.

As an added bonus, the Toeplitz two-source extractor used has the so-called strong property. That is, even conditioned on the knowledge of one input string of weakly random bits, the output bits are still fully random. We refer to the technical notes [1] for discussion, a consequence being that if one provider builds in some backdoors in the provided unit, the random generation scheme is still not broken unless the two providers come together to cooperate.

Putting everything together

Now that we have determined the conditional min-entropy of our physical sources and have an efficient quantum-proof two-source extractor in place, all that remains is to put the two pieces together.

1. First, we specify how many random bits we want to generate, the desired security parameter, and the conditional min-entropy of our weak sources of randomness from the quantum processing units:

1. At the beginning of the notebook, we loaded two separate QPUs as available in Amazon Braket. We now run on the respective QPUs the Hadamard circuit followed by measurements in the computational basis:

   (Note: If preferred, one can alternatively use the pre-loaded on-demand simulator SV1. In this case, please comment out the QPU code in the cell below and instead uncomment the provided SV1 code.)

1. The quantum tasks have now been sent to the respective QPUs and we can recover the results at any point in time once the status is completed:

   (Note: In case you opted to use the on-demand simulator SV1 instead of the QPUs, please do not run the following cell.)

1. We run the Toeplitz two-source extractor on the two sequences of raw random input bits:

1. That is it, above bits are random up to the chosen security parameter!

Beyond current implementation

Different quantum processing units are potentially governed by different noise models. Correspondingly, this will lead to different conditional min-entropy rates for the raw sources of randomness. In this notebook and following the theory notes [1], we can change the noise model for the numerical evaluation of the min-entropy (with all other parts remaining the same).

From a cryptographic viewpoint, the quantum hardware providers as well as Amazon Braket have to be trusted in order to end up with secure random numbers. More broadly, we note that there are more intricate ways of generating randomness from quantum sources than presented here, in particular for the use case when one is not ready to trust the underlying quantum hardware because of potential backdoors inbuilt. Such a so-called (semi) device-independent scheme is for example given in [3], with a corresponding implementation in Amazon Braket [7]. For a general in-depth discussion of QRNGs, we refer to the review article [4], as well as the extensive security report [6].

Literature

[1] M. Berta and F. Brandão, Robust randomness generation on quantum computers, available online.

[2] M. Hayashi and T. Tsurumaru, More Efficient Privacy Amplification With Less Random Seeds via Dual Universal Hash Function, IEEE Transactions on Information Theory, 10.1109/TIT.2016.2526018.

[3] C. Foreman, S. Wright, A. Edgington, M. Berta, F. Curchod, Practical randomness and privacy amplification, arXiv:2009.06551.

[4] M. Herrero-Collantes and J.-C. Garcia-Escartin, Quantum random number generators, Review of Modern Physics, 10.1103/RevModPhys.89.015004.

[5] D. Frauchiger, R. Renner, M. Troyer, True randomness from realistic quantum devices, arXiv:1311.4547.

[6] M. Piani, M. Mosca, B. Neill, Quantum random-number generators: practical considerations and use cases, evolutionQ.

[7] Quantum-Proof Cryptography with IronBridge, TKET and Amazon Braket, A. Edgington, C. Foreman, D. Jones, Cambridge Quantum Computing.