QuantumRNG-aaS - Making use of Quantum Algorithms

We have all heard the hype about Quantum Computing...

"Quantum Computers are gonna break everything!!"

"Quantum is coming... the wind is blowing..."

In a world where 'quantum' is equally likely to be used to sell you dishwasher tablets or toilet paper, as much as it is to be used as a way to scare people with headlines like "Quantum Computing and the End of Encryption" (really, really not helpful, Hackaday...) there is now somewhat of a skills rush to be able to have technicians who can make sense of this bold new world of quantum computing.

What this Hacktober project will demonstrate is the following:

• That quantum computing is certainly within the understanding of most of us
• Cloud quantum offerings can be implemented into real-world systems beyond the realm of 'novelty'
• With the right approach, a quantum circuit can be used to provide something actually useful for modern applications.

TL;DR - we're going to work through the theory to arrive at this proof of concept - and then offer up the model that we can build up and collaboratively code as part of the Hacktober activities so that we can arrive at a pretty cool output: Quantum-RNG-as-a-Service! #QRNGaaS

DISCLAIMER - this code is NOT for use in production systems without a significant amount of extra engineering and checking. YMMV and Caveat Developer!!

Primer on Quantum Algorithms

It's impossible to do much with quantum computers at the moment without delving into some deep-tech ideas of what is going on at the fundamental level of a quantum computer - principally discussing the idea of a 'qubit'.

But why do we have to do this? Well, the reason is that quantum computers are much closer to a Z80 processor than they are to a modern Intel i9. And like with the Z80, in order to make them workable, you have to have a good idea what is going on deep under the hood. One day we will have a wonderful, iterative abstraction model for quantum computing - but sadly, that day is not today!

 So what isn't a quantum computer?

Put simply, a quantum computer is not 'just a faster computer'! Quantum algorithms operate in a totally different way to regular, 'classical', computers.

You're not gonna get MS Flight Sim running any better with quantum computers - especially not as they are right now! Quantum computers are still specialist pieces of equipment.

NB - our emphasis for 'quantum computing' here is on the 'computing' rather than the 'quantum' part... so we'll keep this bit brief :P

 So what's the big deal?

The fundamental deal is that quantum technologies (usually, but not exclusively) make use of two quantum effects:

• Superposition - the idea that a particle is in a combination of states simultaneously.
• Entanglement - the idea that two particles can be, in some strict mathematical sense, inseparable to the point that a measurement of one gives you some facts about the other (without measuring it first).

This leads us to the next question - how do you actually do this?

Well, first up, let's discuss the structure of a qubit in comparison to a regular 'bit'. A bit is just a one or a zero - and it is always exactly one OR the other, NEVER both. A qubit, however, can be in some superposition of the 'zero state' and the 'one state' - when you measure it, you will always get just a '1' or a '0' as your output, just like a bit. The difference is that it can be either 0 or 1, with some probability of being one or the other across many measurements.

To understand this better - take a look at the following diagram:

This is called the 'Bloch Sphere' - and it represents the 'sphere' of possibilities for the position of a qubit's state, which we usually write as |ψ⟩.

Now, we do have to do a little maths - as we can't just have any old values wandering around - they won't stay on the surface of the sphere! So, we need to define what |ψ⟩ is - let x and y be complex numbers (that is, of the form m+in where i is the imaginary constant, and m and n are real numbers, aka 'floats'), then we say that |ψ⟩ = a|0⟩ + b|1⟩, letting |0⟩ be the column vector (1,0), and |1⟩ be the column vector (0,1). We only require that |a|^2 + |b|^2 = 1 (to preserve the probabilities of the system and keep the tip of the state vector |ψ⟩ on the sphere surface).

I'm not going to go into things like unitary gates, the 4 postulates of quantum mechanics, linear algebra, inner/outer products, tensor products, seperable states, etc. etc. - if you would like a reasonable primer, look at these slides.

Before we go on - here's an emergency post-mathematics kitten:

 Building things for multiple qubits...

Now, this was actually important for the next piece of the puzzle - how you program a quantum computer! Because everything is now reducible to two-place column vectors that have nice properties - we can now manipulate them easily with 2x2 matrices! This is exactly what forms quantum gates.

But what do we mean by 'quantum gate'? Well, classical computers have logic gates; AND, OR, NOT, NOR, NAND, XOR, etc. which are placed in various combinations to make computer programs. All of our computation is fundamentally reducible to these gates.

In the same way, a quantum algorithm is formed from the composition of quantum gates, these 2x2 matrices, in sequences we call 'quantum circuits' (analogous to 'boolean circuits' for those familiar with them).

 Our first Quantum Circuit!

What do these quantum circuits look like? Well, we can see an example here:

We assume that on the far left, all qubits are set to |0⟩ (with the vector pointing up on the sphere). Now we can apply gates - and some of these gates have special names;

• the circular blue gate with an '+' in the middle is called the 'Pauli X' - this flips the gate from |0⟩ to |1⟩ or a similar inversion if the qubit vector |ψ⟩ isn't wholly up or down.
• The red gate with a 'H' is called the Hadamard Gate, and this serves to put the qubit into superposition - more on this later!
• The circular blue '+' with a tie to an upper qubit is called a CNOT gate - this is a very cool gate that is involved with entanglement and other cool operations on a quantum computer, but which we'll skip over here.
• The black box with a vertical line is the 'measurement' gate.

For the ultimate output, the classical bit 'buffer' is the lowest line in these diagrams - and when we measure qubits we get either a 0 or a 1, and these are placed into the buffer sequentially.

So how do we get an output? Well, the quantum computer will run our circuit more than once, and give us a graph of the outputs - so when I ran the above I got the following output graph:

You will notice that we 'almost always' got a '11' (which if you check the matrices is what we should have gotten) but there is just over 13% of the outputs that were the other three possible states for 2 qubits. This inherent noise is why quantum computers such as these that don't do quantum error correction are called 'Noisy Intermediate Scale Quantum computers' or NISQs.

NB - There is also a Quantum Assembly language called QASM! For the above circuit, it looks like this:

OPENQASM 2.0;
include "qelib1.inc";

qreg q[2];
creg c[2];

x q[1];
h q[0];
h q[1];
cx q[0],q[1];
h q[0];
h q[1];
measure q[0] -> c[0];
measure q[1] -> c[1];

It is also worth mentioning that the above circuit is not what is actually run - the commercial quantum computers implement a reduced set of gates that are equivalent under combinations to every theoretical gate. This transpiling is very common - for the above circuit, the transpiled circuit looks like this:

 Quick aside - resources

I'm skipping over MANY details here, so if you want to learn more have a look at these resources:

• Qiskit Documentation - This has many excellent pages covering the basics of quantum gates, but also in-line summaries of the matrix and vector stuff in case that is a little rusty. A really good resource!
• Quantiki - a really good website with lots of details and descriptions of various quantum algorithms and their uses!

 Building Something Useful

You'll note that I didn't explain what was really going on in the circuit above - it's not that important (it is a circuit that is equivalent to an inverted CNOT, part of the Bernstein-Vazarani algorithm, for the curious). But the next bit will require us to go into some depth - we're going to show how to acquire some of the best quantum-ly random bits from a quantum computer! We can then use these to fold into a local entropy pool for generating random numbers.

 Quantum Supremacy and Randomness

When Google announced quantum supremacy what they had achieved was the measurement of randomness in a few hundred seconds that would take a supercomputer 10,000 years to perform the same fidelity of operation. This is a similar process that companies such as Cambridge Quantum Computing use (we presume, anyway) to measure the randomness of a source and help it be 'better' randomness.

 But who cares about this?

Who would find this useful? Well - consider the following clients and use cases:

• Anyone generating keys or doing cryptography will always need good entropy seeds, and quantum is one of the best sources.
• Anyone doing financial simulations and modelling (such as Monte Carlo sims)
• Anyone doing AI/ML model generation will need plenty of good quality randomness.
• Gaming applications - obviously, when you roll a die in a game, you don't want it being predictable! The gaming industry has very strict requirements on randomness for its purposes.

 Our Grand Design

We are not going to do anything so fancy here - we will, however, use the following algorithm:

1. Put a sequence of qubits into superposition with a Hadamard gate
   • This means each qubit has a balanced probability of 1/2 of going into state 0 or 1 on output, which is our source of randomness.
2. Take this output, and blend it with our local randomness entropy pool.
3. Use this pool to seed a CSPRNG (Cryptographically Secure Pseudo-Random Number Generator) that can generate random numbers very quickly for general use.

The rough block diagram is here:

So we will setup a background job to use the IBM-Q python API in qiskit, and whilst we wait, we will generate random numbers on the fly for as long/as many as we need to provide.

So what does our circuit look like? Well, something like this:

Now, we note the following calculation:

• The 15 maximum qubits on the ibmq_16_melbourne quantum computer means that we can run for 15 random bits of output for each shot.
• The max number of shots is 8,192 (2^14).
• This means that we can get up to 15*8192 = 122,880 bits in the output!
• These aren't secret, as IBM can also know these bits, so we will blend them with local randomness that we can assume is known only to us for this use case.
  • It is important that any input into the RNG is not widely known, else we may compromise our random numbers!
  • For this, we will use SHA3 (Keccak) hashing to keep things as high-entropy as possible. This is a PQC algorithm with a large internal state, so this should maintain a good level of security.

And this is the core of our service! 😁

 But what is there to hack?

Well, so far - this just shows how to generate random numbers locally from a class with the background process occasionally asking IBM-Q very nicely! (NB - you'll need an IBM-Q account and API token for the script, but these are free!!)

What can we build? Well, consider the following:

• MQTT randomness source - there are projects such as Entropy Broker that allow you to 'import' entropy from various sources. We can maybe write these to support MQTT and then distribute randomness across a network (with appropriate levels of security, ofc!) to better seed local entropy pools.
• A Randomness API! - We could build a python API that would allow us to provide high-quality randomness derived from our beautiful quantum-ly random bits to anyone who asks, in bulk, and at scale!

Or anything else you can think of to get good quality randomness to those who need it!

 Show us the money!

For those who want to see a PoC flask-based API service (only two endpoints, but it should be quite illustrative) then have a look at the following github repo:

Santandersecurityresearch / QuantumRNG

A Quantum computer based CSPRNG, written in python, as a PoC for using QCs in services.

But if you want an all-in-one script to play with, we have that, too! Now I have discussed the base theory - here is the proof-of-concept script!

	__author__ = "Mark Carney aka @LargeCardinal"
	__copyright__ = "The Author"
	__license__ = "MIT"
	__status__ = "Proof of Concept - NOT FOR PRODUCTION"
	import qiskit
	from qiskit import IBMQ
	import math
	import sympy
	import secrets
	import threading
	import hashlib
	IBMQ_API_TOKEN = ''
	class QuantumRNG(object):
	def __init__(self, ibmqx_token=''):
	self.sys_rng = secrets.SystemRandom()
	self.qc_entropy_pool = "{0:b}".format(self.sys_rng.randrange(3*10**100,4*10**100))
	self.seed = secrets.randbelow(5*10**100)
	# prepare the first seeds and fix the random primes
	# for the CSPRNG
	x = self.sys_rng.randrange(3*10**100, 4*10**100)
	y = self.sys_rng.randrange(3*10**100, 4*10**100)
	self.p = self.next_usable_prime(x)
	self.q = self.next_usable_prime(y)
	self.reseed_count = 0
	self.reseed_threshold = 10**7 #reseed every 10 million bits - reduce this to test the IBMQ integration. -MC
	# do qiskit-y stuff
	self.provider = self.set_ibmq_provider(ibmqx_token)
	self.rng_circuit = self.make_circuit(15)
	self.ibmq_backend = self.provider.get_backend('ibmq_16_melbourne')
	# small CSPRNG from here: https://www.johndcook.com/blog/2017/09/21/a-cryptographically-secure-random-number-generator/
	# tweaked to match the original paper (not using mod 2, but the proper parity of the output from x*x mod M)
	# the Blum-Blum-Shub algorithm has some critical analysis here - https://arxiv.org/pdf/1811.06418.pdf
	# original is here: https://pdfs.semanticscholar.org/c19b/91cdc1da67c52e606cd4752472ce0db83131.pdf
	def next_usable_prime(self, x):
	# Find the next prime congruent to 3 mod 4 following x.
	p = sympy.nextprime(x)
	while (p % 4 != 3):
	p = sympy.nextprime(p)
	# Check the seed mod p isn't 0...
	if self.seed % p == 0:
	p = self.next_usable_prime(p+1)
	return p
	def get_rand_bitstring(self, N=64):
	M = self.p*self.q
	#print("count is {0}".format(self.reseed_count))
	if self.reseed_count > self.reseed_threshold:
	self.do_update_entropy()
	x = self.seed
	bit_string = ""
	for _ in range(N):
	x = x*x % M
	# Turns out we probably don't need the fancy parity,
	# just odd/even parity will do. -MC
	b = x % 2
	bit_string += str(b)
	# update the seed
	self.seed = x
	# update bit count
	self.reseed_count += N
	if self.reseed_count % 8196 == 0:
	print("[i] Random bits at count {0} are: {1}".format(self.reseed_count, bit_string))
	return bit_string
	# Convert the bitstring to bytes - useful for various applications. -MC
	def get_rand_bytes(self, N=64):
	bitstring = self.get_rand_bitstring(N=N)
	v = int(bitstring, 2)
	b = bytearray()
	while v:
	b.append(v & 0xff)
	v >>= 8
	return bytes(b[::-1])
	def update_seed(self, new_seed):
	self.seed = new_seed
	return
	def do_update_entropy(self):
	#print("doing entropy update...")
	# use system entropy in times of need
	if len(self.qc_entropy_pool) < 512:
	# Just copying bits from the local entropy pool for now... Not very elegant :-/ -MC
	local_bits = "{0:b}".format(self.sys_rng.randrange(2*10**100, 3*10**100))
	self.qc_entropy_pool += local_bits
	print("[!] Added {0} bits from local entropy pool...".format(len(local_bits)))
	if len(self.qc_entropy_pool) < 1025: # we don't want to call too much...
	# use background thread to get quantum bits... Get 1024 bits in 15-bit chunks across so many shots on the QC. -MC
	# the queues might be long, so we just have to wait...
	get_qc_thread = threading.Thread(target=self.get_quantum_bits, name="IBM-QX Computation", args=(1024,))
	get_qc_thread.start()
	# consume 64-bits of entropy...
	self.seed += int(self.qc_entropy_pool[:256],2)
	# remove the bits we used...
	self.qc_entropy_pool = self.qc_entropy_pool[256:]
	print("[!] Remaining bits in entropy pool: {0}".format(len(self.qc_entropy_pool)))
	# reset the count
	self.reseed_count = 0
	return
	# IBM-QX stuff inspired by: https://github.com/ozanerhansha/qRNG/
	def set_ibmq_provider(self, ibmqx_token):
	if ibmqx_token == '':
	provider = qiskit.BasicAer
	else:
	IBMQ.save_account(ibmqx_token, overwrite=True)
	IBMQ.load_account()
	provider = IBMQ.get_provider('ibm-q')
	return provider
	def make_circuit(self, n=15):
	# This quantum circuit takes n-many qubits, and then puts them into
	# superposition with a Hadamard operation (transpiled to a Z-rotation, usually).
	# We then measure each qubit and put the ouputs into a register of n-bits in length
	# and then return that back. -MC
	qr = qiskit.QuantumRegister(n)
	cr = qiskit.ClassicalRegister(n)
	circ = qiskit.QuantumCircuit(qr, cr)
	circ.h(qr)
	circ.measure(qr,cr)
	return circ
	def get_bits_from_counts(self, counts):
	bits = ""
	for i in [k for k, v in counts.items() if v == 1]:
	bits += i
	return bits
	def run_ibmq_circuit(self, shots=35):
	# our circuit will have 2^n bits of entropy of output, but the maxmimum number of shots allowed
	# on the big IBMQ 16-qubit machine in Melbourne is 2^14... so in theory we can run this
	# up to 2^14 times, and get 15 bits each time with little risk of things overlapping!
	# (Why? Because pigeonhole principle, and random...)
	# Thus in one job we can theoretically get up to 122,880 (15*8292) bits of good, pure,
	# quantumly-derived entropy! :-D The only problem; it isn't secret to us...
	if self.ibmq_backend.remaining_jobs_count() > 4:
	# if enough jobs are left en queue...
	job = qiskit.execute(self.rng_circuit, self.ibmq_backend, shots=shots)
	bits = self.get_bits_from_counts(job.result().get_counts())
	else:
	print("[!] No free jobs - using system randomnes...")
	#return some system-y randomness
	bits = "{0:b}".format(self.sys_rng.randrange(2*10**100, 3*10**100))
	return bits
	def get_quantum_bits(self, n=512):
	print("[*] running bg IBMQ process")
	# default to get ceil(512/15) random bits from QC ...
	numshots = math.ceil(n/self.rng_circuit.width()*2)
	# go get the quantum! -MC
	bits_from_qc = self.run_ibmq_circuit(shots=numshots)
	# hash everything to make the most of the quantum :P
	current_e_pool = self.qc_entropy_pool
	# clear the pool.. or not -MC
	#self.qc_entropy_pool = ""
	m = hashlib.sha3_512()
	# Mixing it up twice by hashing the new bits and the old pool both ways...
	# This is basically using Keccak as an 'entropy expander' twice.
	# Reason for this is that our quantumly random bits aren't secret to only us,
	# and the entropy may be mismatched with our local os.urandom output,
	# so this should normalise it. :-) -MC
	for i in range(math.floor(len(bits_from_qc)/512)):
	m.update(str(current_e_pool + bits_from_qc[i*512:(i+1)*512]).encode('utf-8'))
	self.qc_entropy_pool += ''.join(format(byte, '08b') for byte in m.digest())
	m.update(str(bits_from_qc + current_e_pool).encode('utf-8'))
	self.qc_entropy_pool += ''.join(format(byte, '08b') for byte in m.digest())
	print("[i] Updated the entropy pool with {0} bits from IBMQ, {1} bits after hashing...".format(len(bits_from_qc),(math.floor(len(bits_from_qc)/512)+1)*512))
	return
	def main():
	q_rng = QuantumRNG(ibmqx_token=IBMQ_API_TOKEN)
	for i in range(2*10**7): # get some req's for 64-bits from CSPRNG for test...
	q_rng.get_rand_bitstring()
	if __name__ == "__main__":
	main()

view raw QuantumRNG-POC-draft.py hosted with ❤ by GitHub

Special thanks to Dr. Joe Wilson (@jmaw88) for his help in proofreading this post. :)

Comments

[imtarajones]

This is great. Thank you for writing genuinely useful quantum computing content and not just clickbait of chatgpt. Would LOVE to subscribe to more of these, so please do keep them coming. I'm somewhat new to this space as my role has some quantum computing work (high level programming and integration as my team experiments with something related to our field). So love reading this stuff :)