Generating quantum randomness with Amazon Braket

Introduction – the need for randomness

Random numbers are a crucial resource used throughout modern computer science. For example, in computation, randomized algorithms give efficient solutions for a variety of fundamental problems for which no deterministic algorithms are available. This includes Monte Carlo methods that have widespread applications in science for the simulation of physical, chemical and biological systems, or applications in finance and business for options pricing and stochastic modeling.

Random numbers are equally fundamental in cryptography and cybersecurity. They are at the heart of widely used schemes to create keys for encryption and secure communication. For such security applications, it is also essential that the random numbers employed are kept private from any third party, especially malicious ones. The following post focuses on cryptographic applications and describes how quantum random number generators (QRNGs) hold promise to enhance security for certain use cases.

This post discusses how to create private random numbers using multiple quantum processing units (QPU) available in the Amazon Braket quantum computing service. All of the code and technical material from this blogpost is available here in Amazon Braket Examples Github repo.

Ways to create randomness today

What exactly is randomness, and how is it created? For a simple example, you can flip a coin, assign the two possible outcomes the values zero and one, and repeat this procedure many times. This leads to a string of random bits – as long as the coin is fair with a 50% probability for each of the two possible outcomes.

It turns out that the first step in modern random number generators works similarly, but instead of flipping a physical coin, you use ring oscillators with additional post-processing as the physical source of unpredictability. An example of such hardware random number generators (HRNGs) is Intel’s Ivy Bridge central processing unit that comes with a built-in digital random number generator.

The second step in randomness generation is to input these relatively few bits of physically generated raw randomness as a seed into pseudo-random number generators (PRNGs). These are deterministic algorithms that generate long sequences of numbers, whose properties approximate the statistical properties of random numbers. For more on the inner workings of PRNGs, refer to “A Primer on Pseudorandom Generators” by Oded Goldreich.

As PRNGs are based on certain computational assumptions, in principle, attackers with unbounded computational power could correctly guess the numbers produced by PRNGs. However, cryptographic versions of pseudo-random number generators (CPRNGs) are certified according to the latest standard of the National Institute of Standards and Technology (NIST). As such, state-of-the-art implementations of this classical technology for generating randomness sufficiently address nearly all of today’s needs.

Nevertheless, as the security of cryptographic protocols crucially depends on high-quality randomness, security researchers and teams in large organizations may want numbers that are random and private, independent of any computational assumptions. Reasons for this include protecting high-value assets and critical systems in virtualized cloud environments in the military, governmental, and financial sectors, as well as more niche applications such as quantum cryptography or the signing of cryptocurrency transactions.

Though rare, there have been random number generator attacks in the past that rendered existing cryptographic schemes insecure. There are potential downsides of carelessly implemented PRNGs:

• Just as a physical coin being flipped might be biased or its movement could be foreseeable by a computationally powerful attacker, HRNGs are only as random as their underlying physical sources are unpredictable.
• The manufacturers of HRNGs have to be trusted on the inner workings of their devices. Even though one can run statistical tests on the output of HRNGs, it is in principle impossible to verify that the created bits are indeed random. For example, an HRNG in Internet of Things (IoT) devices can fail to produce proper randomness when too many random numbers are needed too quickly.
• PRNG are only computationally secure and hence do not provide everlasting security against future technological advances. Moreover, certifications such as from NIST are susceptible to potential backdoors, as showcased by this critical example.
• Virtualized PRNG might inadvertently reuse the same source in multiple instances, leading to different machines creating the same “random numbers”.

These potential vulnerabilities of classical technologies for generating randomness can be addressed with quantum technologies that make use of the inherent unpredictability of the physics of microscopically small systems. Now, I describe the basics of how using quantum technologies for randomness generation works, and explain how you can implement quantum random number generators (QRNGs) using the quantum processing units (QPUs) available in Amazon Braket.

How quantum computers provide randomness

The main conceptual differences between classical and quantum random number generation are:

• For the first step of QRNG, the raw randomness collection is not based on classical physics as the is the case with ring oscillator based HRNGs, but rather based on quantum physics. Unique quantum features thereby allow the creation of freshly generated randomness that provably cannot be known by anyone else in advance.
• In the second step of QRNG, the raw randomness is not put into PRNGs, but rather into randomness extractors (REs). These are classical algorithms that combine multiple sources of potentially weakly random bits into one output string that becomes (nearly) perfectly random. Importantly, no computational assumptions are introduced as the post-processing with REs condenses all the physical randomness from the different sources.

Taken together, simple protocols based on quantum hardware and classical post-processing allow the creation of (nearly) perfect physical randomness without relying on computational assumptions. As an added bonus, certain device-independent protocols enable you to self-test the quantum hardware used, and find any potential backdoors installed by the manufacturer.

There are various concrete technologies and protocols for QRNG, and all come with their own advantages and disadvantages. For a detailed discussion on these, read the article “Quantum random number generators” by Miguel Herrero-Collantes and Juan Carlos Garcia-Escartin.

Using two QPUs to generate randomness

The approach I use below focuses on a simple QRNG implementation based on today’s available QPUs – not the implementations of QRNGs based on specific quantum hardware purpose-built for randomness generation. These noisy and intermediate scale quantum (NISQ) QPUs are fully operational quantum computers that can be programmed to run arbitrary circuits up to a certain depth and qubit limit due to the inherent noise in the device.

The basic idea behind our approach is to make use of the superposition principle in quantum mechanics to produce n qubits in the equal superposition state:Then you measure each qubit in the standard basis {|0><0|,|1><1|}. By the mathematical rules of quantum mechanics, each qubit state will collapse to either zero or one with exactly 50% probability. This leads to an n bit string, and if all operations are performed perfectly, the outcome is inherently random. This means that even though you start out with complete information about the quantum state, the information to which value each qubit will collapse when measured is, in principle, impossible to know beforehand. Note that this contrasts with classical randomness generators which rely on complex systems governed by classical physics – where the randomness comes from a lack of information about the underlying state of the system.

The catch is of course that you cannot fully rely on today’s QPUs as they are noisy. Additionally, as information is never destroyed in quantum physics, information about the noise actually leaks into the environment. This gives a potential attacker quantum information about the measurement outcomes obtained in the QPU.

We can overcome these problems by: (i) using two independent QPUs, (ii) upper bounding the noise in each QPU, thereby making sure that overall, the quantum effects dominate over the noise occurring in the unit, and (iii) doing classical post-processing on the two n bit strings of weak randomness obtained by means of two-source randomness extractors (RE) leading to one shorter m < 2n bit string of now truly random bits.

This is where Amazon Braket comes in handy, with QPUs from different providers readily available. As the QPUs are provided by different companies, they are independent, which is crucial for this architecture to work properly. Moreover, even if one provider builds a backdoor in the QPU that could impair randomness, the scheme is not broken unless the two providers come together to cooperate.

How to build quantum randomness with Amazon Braket

To build this yourself, you can follow along in the Randomness Jupyter notebook in the Amazon Braket Github repo under examples / advanced_circuits_algorithms. It includes a research note detailing the theory and implementation of aforementioned two-QPU QRNG construction. A basic understanding of quantum states and quantum measurements is sufficient to work through the tutorial.

Prerequisites:

• Sign up for an AWS account.
• Enable and log into to Amazon Braket
• Run the Jupyter notebook “Robust randomness generation on quantum processing units,” either in local development environment or in an Amazon Braket managed notebook environment.

Please note, running this notebook in standard form incurs an estimated cost of $2 from QPU tasks on Rigetti Aspen-9 and IonQ (please refer to the AWS Pricing Calculator for Amazon Braket for the latest pricing information). Alternatively, you can run the notebook for free by modifying the code to replacing QPU devices with the local simulator or SV1 as part of the AWS Free Tier. Of course, this would provide imperfect randomness, as the quantum circuit simulators use a classical computer.

Getting started creating randomness with Amazon Braket

Now to get started, the first step in the Jupyter notebook is to run the following basic Hadamard circuit to create raw strings of (non-perfect) random bits.

Figure 1: A basic Hadamard circuit to create raw strings of (non-perfect) random bits.

To create raw strings of random bits

1. Set this up as a test run in the SDK’s local simulator by using the following Python code:

# AWS imports: Import Braket SDK modules
from braket.circuits import Circuit

# set up local simulator device
device = LocalSimulator()

# function for Hadamard cirquit
def hadamard_circuit(n_qubits):
    """
    function to apply Hadamard gate on each qubit
    input: number of qubits
    """

    # instantiate circuit object
    circuit = Circuit()

    # apply series of Hadamard gates
    for i in range(n_qubits):
        circuit.h(i)
    return circuit

2. Run this Hadamard circuit with n = 5 qubits for m = 1 shots.

# define circuit
n_qubits = 5
state = hadamard_circuit(n_qubits)
# print circuit
print(state)

# run circuit
m_shots = 1
result = device.run(state, shots = m_shots).result()

# get measurement shots
counts = result.measurement_counts.keys()

# print counts
list_one = list(counts)[0]
array_one = np.array([list_one])
print("The output bit string is: ",array_one)

This should result in the following message:

Figure 2: Measurement results for 5 qubit Hadamard circuit test run.

To overcome this problem, you will run above Hadamard circuit on two independent QPUs.

Figure 3: Using two NISQ QPUs and classical post-processing to generate randomness.

The raw bits from the QPUs are fed into a randomness extractor that filters out the relevant noise. Next, there are some crucial technical portions of the notebook that are too extensive to delve into here. In summary, you model the noise affecting the QPUs, together with a cryptographically secure design and efficient implementation of the randomness extractor.

In the end, you run Hadamard circuits of size 141 on the QPUs from Rigetti and IonQ and extract 10 cryptographically secure bits.

Figure 4: (i) Set up desired output size, with needed input size dictated by chosen security parameter, (ii) Raw strings of (non-perfect) random bits, (iii) Output of 10 (nearly) perfect random bits.

If you are interested in more content on QRNGs and Amazon Braket, Cambridge Quantum Computing recently published an approach for a complementary QPU-based QRNG, IronBridge. In contrast to our basic implementation for pedagogical purposes, the Cambridge Quantum Computing approach works in the (semi) device-independent setting, enabling a certain level of self-testing. For more information on their work, refer to the research paper “Practical randomness and privacy amplification” and the blog post on the implementation of the IronBridge Circuits in Amazon Braket.

Conclusion

This post discussed the basic need for random numbers in cryptography, introduced the pros and cons of classical and quantum technologies for randomness generation, and finally described an implementation of a quantum random number generator in Amazon Braket, that you can try yourself.

More broadly, who should be using QRNGs at an industrial scale at this point? The honest answer is that we do not have a satisfactory answer to this question yet, as carefully managed cryptographic PRNGs address nearly all of today’s needs. Nevertheless, continued progress on quantum technologies will make QRNGs cheaper and more accessible, potentially leading to an important role in high-security applications. For a more detailed comparison of real world cryptographic PRNG and QRNG for cryptography, you can read the extensive report, “Quantum Random-Number Generators: Practical Considerations and Use Cases” by EvolutionQ.

Today, generating high-quality random numbers based on quantum technologies represents an excellent application of NISQ QPUs. If you are performing your own research in quantum computing and are considering working with AWS, please refer to our Amazon Quantum Computing Research page to learn how we may be able to help you.

Acknowledgements

Thanks to Antia Lamas-Linares for discussions on quantum cryptography that helped inform this post.