### Why Quantum Computers Threaten Random Number Generation

The goal of a random number generator is to produce completely unbiased and private streams of random bits. Each bit should have a 50% chance of being a zero or a one, with an attacker having no ability to predict this. This is what makes them usable in cryptography.

Today, there are three broad approaches to randomness generation. The first is to use pseudo-random number generators (PRNGs), which use software algorithms to expand an initial “seed” value into a random-looking sequence of bits. Because PRNGs are deterministic, the output is completely predictable to anyone who can figure out the seed.

The second approach measures erratic physical systems to produce random outputs. In this category are so-called true random number generators (TRNGs) and many existing quantum random number generators (QRNGs). In a TRNG, the physical system being measured is a predominantly classical process, such as thermal noise in a diode. QRNGs observe the results of quantum processes, such as the route a photon takes when it hits an angled silvered mirror.

The approaches described above all suffer from the same problem: they are completely dependent on correct physical construction and perfect modelling of the random number generator. In short, the device has to be completely trusted.

As we mentioned above, a quantum computer is well suited for modelling complex physical systems. As a result, a quantum adversary could potentially model these devices and predict their output. Even a non-quantum adversary could begin to predict the output if the device degrades over time: a common issue in complex physical systems involving lasers and precise angles. So in terms of post-quantum security, these RNG approaches are fundamentally flawed.

Fortunately, there is a third approach, which we will discuss in this article. Cambridge Quantum Computing has developed the first provable QRNG, known as IronBridge, which uses quantum computers to generate unbiased private entropy. Unlike the other two approaches, this is invulnerable to a quantum adversary, and it produces self-tested randomness.

IronBridge generates cryptographic keys using this entropy, resulting in quantum-proof keys (for both classical and post-quantum algorithms). Such keys are invulnerable to the most powerful quantum attacker.

### How IronBridge Generates Keys Using Quantum Computers

IronBridge relies on the intrinsic randomness of quantum-mechanical systems. Unlike standard QRNG approaches, we treat the quantum computer as a black box and pass it circuits to execute. The output of the circuits is used to generate our entropy, as well as acting as a self-test to ensure the quantum computer is functioning correctly. This means we no longer have to place complete trust in the device.

More specifically, IronBridge takes imperfect (biased or not fully private) randomness and amplifies it using a quantum computer, resulting in perfectly unbiased and private data with unconditional security. This verified randomness and privacy amplification is only possible with quantum devices, thanks to the physical phenomenon of entanglement, which allow us to exhibit quantum effects from a device without having to characterise it. By comparing the inputs and outputs we can quantify the entanglement in the device and obtain an explicit value for the error in the device.

We measure the quantum effect by running a Bell test, which can be viewed as a test for “quantum correlations”. Certain correlations between inputs and outputs are exclusively quantum and can only be achieved if the device uses entanglement, assuming there are no loopholes in the test setup.

In our protocol, we use a three-qubit Bell test to evaluate the Mermin correlator M. This results in a value between zero and four, where anything above two indicates quantum correlations (i.e. entanglement). Furthermore, the value of M tells us how much entanglement was exhibited, thus quantifying the performance of the device. This value dictates how much randomness and privacy the outcomes have (see here for further technical details), allowing us to extract only the intrinsic quantum randomness. If M is not greater than 2, we abort the protocol.

Recently, we’ve made improvements to the protocol, allowing for increased randomness generation rates. We continue to work with our partners and academic collaborators to optimise and improve our protocol, both in terms of hardware-specific implementation and theoretical analysis.

You can read more about our entropy generation protocol in our paper; this is the heart of our IronBridge platform and creates the raw entropy we use to generate our quantum-proof cryptographic keys. But now we’ll move on to running these circuits using Amazon Braket.

### Running IronBridge Circuits on Amazon Braket

To test the protocol on Amazon Braket, we ran four different three-qubit IronBridge circuits on an IonQ device. The circuits were composed of H, CX, S and Sdg gates. These are all supported by the Braket SDK. Therefore the only thing we needed to do before passing the circuit to the BraketBackend was a noise-aware placement of the qubits:

from pytket.routing import NoiseAwarePlacement

NoiseAwarePlacement(backend.device()).place(circuit)

The above line assigns the circuit’s logical qubits to physical nodes on the device, taking into account the device architecture and noise characteristics (which are obtained from Braket when the backend object is constructed).

This device allows a maximum of 10,000 shots per job. Our experiment was split over several jobs running successively, and the results accumulated until we had a million shots per circuit. This took about 24 hours of elapsed time.

Once the experiment was complete, we calculated the Mermin correlator M. In this case,

M = |<001> + <010> + <100> – <111>|

Where <> denotes the correlator function for one of the circuits, i.e. the probability of even parity in outputs minus probability of odd parity in outputs. The bit strings encode different circuits. For example,

<001> = [P(000|001) + P(011|001)+ P(101|001) + P(110|001)] – [P(001|001) + P(010|001) + P(100|001) + P(111|001)]

where P(m|c) is the probability of measuring m given the circuit encoded by c.

The result of our IonQ experiment was M = 3.702. This is above the classical maximum of 2, proving that the device exhibits quantum correlations (it must have used entanglement). In fact, this value for the Mermin correlator is higher than any publicly reported in literature as far as we are aware, on either quantum computers or single-purpose devices. It is close to the theoretical maximum of 4, showing that small qubit devices are starting to reach maturity with very low error rates.

### Contact Us to Learn More and Trial the Technology

If you would like to trial our QRNG technology, get in touch with us. We are happy to share examples of our entropy for statistical testing or to discuss proof-of-concept and production deployments.

We continue to optimise the protocol and physical implementations to improve generation rates and further reduce the minimal underlying security assumptions. We work with our collaborators to run on different hardware, including devices from IBM, AQT and Honeywell.

This concludes our overview of generating perfect randomness on quantum computers. If you want to try out TKET and Amazon Braket for yourself, read on for a quick how-to.

### Tutorial: Using Amazon Braket with Cambridge Quantum TKET

TKET is an advanced quantum compiler that can interface with a wide range of hardware, handling the full cycle of compilation, dispatch and results retrieval via a unified Python interface. The compilation steps can be controlled by the user to suit the nature of the quantum circuit being run. Each backend also defines a set of default compilation passes at different optimisation levels, chosen to give good results in most cases. When device calibration data are available, these passes take care of placing the logical qubit on the physical device to minimise the overall noise and achieve the most accurate results possible.

AWS Braket serves as a portal to a variety of quantum hardware, currently including:

- Quantum annealers (from D-WAVE);
- Trapped-ion gate-model devices (from IonQ);
- Superconducting gate-model devices (from Rigetti)

It also offers access to two powerful simulators: a state-vector simulator with a capacity of 34 qubits, and a tensor-network simulator with a capacity of 50 qubits for suitably sparse circuits.

Using the pytket-braket extension, TKET can use Braket to run circuits on all its gate-model devices and simulators. It does not support annealers.

Because Braket devices provide detailed calibration data, we can take full advantage of TKET’s noise-aware placement and routing. A TKET Device constructed via a BraketBackend contains the full error characteristics of the device.

### Getting Started

First, install the latest versions of pytket and pytket-braket:

pip install –upgrade pytket pytket-braket

To use the Braket backends you will need an AWS Braket account. Then set up credentials on your local machine using boto3: please see the instructions here. You will need to set up an Amazon S3 bucket and folder where the results are stored. (The examples below use a bucket called “amazon-braket-test” and a folder called “test-folder”).

### Running Circuits

Let’s create a very simple circuit in pytket and then run it on the IonQ device through Braket.

Here’s a 2-qubit circuit that generates a Bell state:

from pytket import Circuit

bell_circ = Circuit(2).H(0).CX(0,1)

Note that we didn’t add any measurement gates to the circuit. At the end of each run, all qubits are measured automatically.

Now we’ll construct the BraketBackend for the IonQ device:

from pytket.backends.braket import BraketBackend

S3_BUCKET = “amazon-braket-test”

S3_FOLDER = “test-folder”

ionq_backend = BraketBackend(

s3_bucket=S3_BUCKET,

s3_folder=S3_FOLDER,

device_type=”qpu”,

provider=”ionq”,

device=”ionQdevice”,

)

The device_type, provider and device arguments all come from the device’s ARN as shown on the Amazon Braket page describing the device. (In this case, the ARN is arn:aws:braket:::device/qpu/ionq/ionQdevice.) That page also shows whether the device is currently available or when it will next be.

Now we need to compile the circuit for the backend device. At a minimum, this involves converting it to the target gate set and placing the qubits. We can control the optimisation level used in compilation, but let’s just use the default:

ionq_backend.compile_circuit(bell_circ)

Let’s run the circuit 20 times on the device.

job_handle = ionq_backend.process_circuit(bell_circ, n_shots=20)

This sends a request to Amazon Braket to run the circuit on the specified device. It may take a few seconds or minutes to complete, depending on availability and load. We can query its status:

print(ionq_backend.circuit_status(job_handle))

Eventually, this should show the status of COMPLETED. Let’s get the result of the experiment:

result = ionq_backend.get_result(job_handle)

This will return immediately if the job is completed; otherwise, it will block until the job has run.

TKET will have selected 2 of the 11 device qubits to run the circuit on, and Braket will have measured to the corresponding bits. When interpreting results we need to know what these bits are. The following short function can be used to get this information.

from pytket.circuit import Bit

def get_cbits(backend, circuit):

return [Bit(backend.device().nodes.index(q)) for q in circuit.qubits]

cbits = get_cbits(ionq_backend, bell_circ)

Let’s have a look at the counts:

counts = result.get_counts(cbits=cbits)

print(counts)

Hopefully, we’ll see something like this:

Counter({(0, 0): 11, (1, 1): 9})

In this case, every shot resulted in the expected 00 or 11 measurement, with about equal probability.

### Diversion: Quantifying Noise

As a quick and light-hearted demonstration of the kind of experiment we can perform using TKET and Amazon Braket together, let’s have a competition between the two gate-model machines. We’ll construct an 11-qubit circuit that “secretly” implements the identity, optimise it for the two platforms using TKET, run it, and then see which comes closest to outputting the zero state.

We have to be a bit sneaky to construct an identity circuit that TKET can’t optimise to nothing, but “here’s one I made earlier” (with the help of the new three-qubit unitary decomposition function from Cirq):

OPENQASM 2.0;

include “qelib1.inc”;

qreg q[3];

u3(1.5*pi,0.0*pi,1.5*pi) q[0];

u3(0.5*pi,0.75*pi,1.25*pi) q[1];

u3(0.5*pi,0.0*pi,1.0*pi) q[2];

cx q[1],q[2];

u3(0.25*pi,0.25*pi,1.75*pi) q[1];

cx q[1],q[2];

u3(0.5*pi,0.0*pi,0.25*pi) q[1];

u3(3.5*pi,1.75*pi,0.0*pi) q[2];

cx q[2],q[0];

u3(0.5*pi,1.75*pi,0.0*pi) q[0];

cx q[1],q[0];

u1(0.25*pi) q[0];

cx q[2],q[0];

u1(0.25*pi) q[0];

cx q[1],q[0];

u3(1.5*pi,1.5*pi,1.75*pi) q[0];

u3(0.5*pi,0.75*pi,1.25*pi) q[1];

cx q[2],q[0];

u1(0.5*pi) q[0];

u3(0.5*pi,0.0*pi,0.5*pi) q[2];

cx q[1],q[2];

u3(0.25*pi,0.25*pi,1.75*pi) q[1];

cx q[1],q[2];

u3(0.5*pi,0.0*pi,0.25*pi) q[1];

u3(3.5*pi,0.25*pi,0.0*pi) q[2];

cx q[2],q[0];

u3(0.5*pi,1.75*pi,0.0*pi) q[0];

cx q[1],q[0];

u1(0.25*pi) q[0];

cx q[2],q[0];

u1(0.25*pi) q[0];

cx q[1],q[0];

u1(0.25*pi) q[0];

cx q[2],q[0];

Don’t believe me? OK, let’s check using a statevector simulator. As it’s such a small circuit, rather than use the remote simulator we can make use of the local simulator included in the Braket SDK and also usable through TKET:

import numpy as np

from pytket.qasm import circuit_from_qasm

c_id3 = circuit_from_qasm(“q3_id.qasm”)

sv_backend = BraketBackend(local=True)

c = c_id3.copy()

sv_backend.compile_circuit(c)

h = sv_backend.process_circuit(c)

r = sv_backend.get_result(h)

sv = r.get_state()

zero_sv = np.zeros(8, dtype=complex); zero_sv[0] = 1

assert np.allclose(sv/sv[0], zero_sv)

Yes, c_id3 is the identity. Now let’s make a big 11-qubit circuit by appending 5 copies of this 3-qubit circuit cyclically:

from pytket.circuit import OpType

c_id11 = Circuit(11)

qbs = [0, 1, 2]

for _ in range(5):

c_id11.add_circuit(c_id3, qbs)

for i in range(3):

qbs[i] += 2; qbs[i] %= 11

print(f”c_id11: depth = {c_id11.depth()}, CX count = {c_id11.n_gates_of_type(OpType.CX)}”)

This circuit has depth 124 and a CX count of 70.

Let’s use TKET to optimise it for the IonQ and Aspen-8 devices. As it has no special structure we will simply use the default compilation passes, at the maximum level of optimisation.

rigetti_backend = BraketBackend(

s3_bucket=S3_BUCKET,

s3_folder=S3_FOLDER,

device_type=”qpu”,

provider=”rigetti”,

device=”Aspen-9″,

)

ionq_c = c_id11.copy()

ionq_backend.compile_circuit(ionq_c, optimisation_level=2)

rigetti_c = c_id11.copy()

rigetti_backend.compile_circuit(rigetti_c, optimisation_level=2)

ionq_h = ionq_backend.process_circuit(ionq_c, n_shots=8192)

rigetti_h = rigetti_backend.process_circuit(rigetti_c, n_shots=8192)

Let’s have a look at the depth and CX count of the compiled circuits:

print(f”ionq : depth = {ionq_c.depth()}, CX count = {ionq_c.n_gates_of_type(OpType.CX)}”)

print(f”rigetti: depth = {rigetti_c.depth()}, CX count = {rigetti_c.n_gates_of_type(OpType.CX)}”)ionq : depth = 228, CX count = 65

rigetti: depth = 280, CX count = 138

The CX count of the Rigetti device is much higher because of the need for routing to the architecture of the device. Sooner or later we will get the results:

ionq_r = ionq_backend.get_result(ionq_h)

rigetti_r = rigetti_backend.get_result(rigetti_h)

With such deep circuits, we must expect a lot of noise in the results. Since we know the ideal result is the zero state, a cheap and cheerful measure of the noise is the average proportion of 1 bits in the measured output.

def noise_level(result, cbits):

counts = result.get_counts(cbits=cbits)

n_ones, n_bits = 0, 0

for bits, count in counts.items():

n_ones += count * sum(bits)

n_bits += count * len(bits)

return n_ones / n_bits

ionq_cbits = get_cbits(ionq_backend, ionq_c)

rigetti_cbits = get_cbits(rigetti_backend, rigetti_c)

print(“ionq : noise =”, noise_level(ionq_r, ionq_cbits))

print(“rigetti: noise =”, noise_level(rigetti_r, rigetti_cbits))

Here are the results:

ionq : noise = 0.2552712180397727

rigetti: noise = 0.48872514204545453

We see that in this case, the IonQ results are significantly less noisy. This could be because the fully-connected architecture removes the need for any routing.

### Simulating Large Circuits

Amazon Braket also has a powerful tensor-network simulator, which can simulate very large circuits (up to about 50 qubits) as long as the entanglement connections are reasonably sparse.

Let’s give it a test drive. Note that the maximum circuit depth for this backend is 100.

c_id50 = Circuit(50)

qbs = [0, 1, 2]

for _ in range(25):

c_id50.add_circuit(c_id3, qbs)

for i in range(3):

qbs[i] += 3; qbs[i] %= 50

tensor_backend = BraketBackend(

s3_bucket=S3_BUCKET,

s3_folder=S3_FOLDER,

device_type=”quantum-simulator”,

provider=”amazon”,

device=”tn1″,

)

tensor_c = c_id50.copy()

tensor_backend.compile_circuit(tensor_c, optimisation_level=2)

print(f”circuit depth = {tensor_c.depth()}, CX count = {tensor_c.n_gates_of_type(OpType.CX)}”)

tensor_h = tensor_backend.process_circuit(tensor_c, n_shots=1)

tensor_r = tensor_backend.get_result(tensor_h)

result = tesnor_r.get_shots()[0]

assert all(x == 0 for x in result)

Simulating this 50-qubit circuit with a depth of 84 and CX count of 325 (after optimisation) is almost instantaneous.

### Get in Touch to Learn More

If you’d like to learn more about any of the topics in this article, such as TKET or our IronBridge QRNG, please contact us.

## CAMBRIDGE QUANTUM ON MEDIUM

Cambridge Quantum’s scientists regularly post on Medium, a hub for social journalism and a hybrid of publications, blogs and publishers.

Follow us there for more of our news and updates.

Read on Medium

TKET

Duncan Jones

Follow Duncan Jones on LinkedIn

Cambridge Quantum GitHub

NIST Competition

Shor’s Algorithm