How to turn a quantum computer into a perfect random number generator

Pure, verifiable coincidence is hard to find. Two new proposals show how to make random numbers factories out of quantum computers.

Say “quantum excellence” at any meeting of computer scientists, and you will probably see them roll their eyes. This phrase refers to the idea that quantum computers will soon cross the line beyond which they will be able to perform tasks that are extremely difficult for classical computers with relative ease. And until recently, these tasks were considered of little use for real applications - hence the rolling of the eyes.



But now that Google’s processor is said to be close to that goal, imminent quantum superiority could have an important use: generating pure randomness.



Randomness is important for almost everything that happens in the computing and communications infrastructure. In particular, it is used to encrypt data that protects everything from ordinary conversations to financial transactions and state secrets.



The true, confirmed randomness - imagine it as a property that exists in a sequence of numbers and makes it impossible to predict the next number in a sequence - is extremely difficult to find.



But this situation may change when quantum computers demonstrate their superiority. These first tasks, which from the beginning simply had to demonstrate the superiority of technology, can also give out a true certified coincidence. “We are happy to welcome this,” said John Martinis , a physicist at the University of California, Santa Barbara, who runs the quantum computing project at Google. “We hope this will be the first use of a quantum computer.”

Randomness and entropy

Randomness and quantum theory go hand in hand like thunder and lightning. In both cases, the former is an inevitable consequence of the latter. In the quantum world, systems are often said to be in a combination of several states - the so-called "Superposition". When you measure a system, it “collapses” into one of these states. And while quantum theory allows you to calculate the probabilities of what you discover when measuring, the exact result will always be fundamentally random.



Physicists have studied this connection in order to create random number generators. They all rely on measurements of some kind of quantum superposition. And although for most methods of generating random numbers that people need, these systems are enough, it can be difficult to work with them. In addition, it is very difficult to prove to the skeptic the true randomness of these random number generators. Finally, some of the most effective methods for generating confirmed randomness require sophisticated designs from multiple devices separated by vast distances.





Google AI Lab Introduces Bristlecone 72-Qubit Quantum Processor In 2018



One recent proposal to extract randomness from just one device - a quantum computer - uses the so-called. the sampling task, which will be one of the first tests of quantum superiority. To understand it, imagine that you were given a box of tiles. On each tile there are several units and several zeros - 000, 010, 101 and so on.



If there are only three bits, then there are eight possible options. However, there may be several copies of each tile in the box. There can be 50 tiles labeled 010 and 25 tiles labeled 001. The distribution of the tiles determines the likelihood that you accidentally pull out a particular tile. In our case, you can pull out tile 010 with a probability two times higher than tile 001.



The sampling task includes a computer algorithm equivalent to randomly pulling tiles out of the box with a specific tile distribution. The higher the probability defined for any tile in the distribution, the more likely the algorithm will pull this tile.



Of course, the algorithm does not pull real tiles out of a real box. It just randomly produces a binary number of 50 bits in length, having received a distribution that determines the desired probability for each of the possible lines of 50 bits in length.



For a classic computer, the complexity of this task grows exponentially with an increase in the number of bits in a string. But for a quantum computer, the task is expected to remain approximately the same for both 5 bits and 50.



A quantum computer begins by saying that all of its quantum bits - qubits - are in a certain state. Let's say they all start with 0. How classic computers can work with classic bits using the so-called. logic gates, and quantum computers manipulate qubits using their quantum equivalent, quantum gates.



However, quantum gates can place qubits in strange states. For example, one kind of gate can place a qubit that starts with a value of 0 in a superposition of 0 and 1. If you then measure the state of a qubit, it randomly collapses to 0 or 1 with equal probability.



Even stranger, quantum gates that can work with two or more qubits at the same time can cause the qubits to become entangled with each other. In this case, the states of qubits are intertwined so that now all these qubits can be described using only one quantum state.



If you bring a bunch of quantum gates to one place, and then make them work with a set of qubits in a certain sequence, this will be a quantum circuit. In our case, to derive a random string of 50 bits, you can build a quantum circuit that places 50 qubits in a superposition of states that describes the distribution you need.



When measuring qubits, the entire superposition randomly collapses into a single 50-bit string. The probability that it collapses into a certain line is determined by the distribution determined by the quantum contour. The measurement of qubits is similar to how a blindfolded person reaches out into a bag and accidentally pulls out one line with the distribution.





Scott Aaronson, Computer Science Specialist, University of Texas at Austin



And how is all this related to random numbers? It is important that the 50-bit string selected by the quantum computer will contain a lot of entropy, a measure of disorder or unpredictability, and therefore randomness. “And this, in fact, can have very serious consequences,” said Scott Aaronson , an IT specialist at the University of Texas at Austin who came up with a new protocol. “Not because it’s the most important use of quantum computers - I think it’s far from it - but because it looks like perhaps the first application of quantum computers that can be put into practice.”



Aaronson's protocol for generating random numbers is pretty simple. A classic computer first collects several random bits from a trusted source, and then uses this “seed of randomness” to generate a description of the quantum contour. Random bits determine the type of quantum gates and the sequence in which they must act on qubits. A classic computer sends a description to a quantum computer that implements a quantum circuit, measures qubits, and sends back a 50-bit string. Thus, it turns out to be randomly selected from the distribution defined by the contour.



Then repeat this process several times — say, 10 times for each quantum circuit. A classic computer uses statistical tests to ensure that the output lines contain a fair amount of entropy. Aaronson showed (partly in a published work written jointly with Lijie Chen and partly in a work yet to be published) that, under certain reasonable assumptions that such tasks are computationally complex, no classical computer can generate such entropy in time comparable to the time during which a quantum computer creates such a random selection from the distribution. After checks, the classic computer collects all 50-bit strings and feeds them to the well-known classical algorithm. “It produces a long, almost perfectly random string,” Aaronson said.

Quantum trap

The Aaronson protocol is best suited to quantum computers with qubits from 50 to 100. When the number of qubits goes beyond these limits, the computational complexity does not allow even classical supercomputers to use this protocol. In this case, another scheme for generating verifiable random numbers using quantum computers enters the scene. It uses an existing mathematical technique with the complex name trapdoor claw-free function. “That sounds worse than the reality,” said Umesh Wazirani , an IT specialist at the University of California at Berkeley, who developed a new strategy that was helped by Zvika Brackerski , Paul Cristiano , Urmila Mahadev and Thomas Vidik .



Introduce our box. Instead of getting into it and pulling out a string, we throw a string of n bits into it, call it x, and then remove another string of n bits. The box somehow matches the input line and the output line. But it has a special property: for each x there is another input line y, which produces exactly the same output line.



In other words, there are two unique input strings - x and y - for which the box returns the same output string z. This triple, x, y and z, is called a claw. Box in the language of computer science - a function. This function is easy to calculate, that is, for any x and y it is easy to calculate z. But if you take only x and z, then finding y - and the whole claw - is impossible even for a quantum computer.





Urmila Mahadev, Umesh Vazirani and Thomas Vidik



The only way to get the whole claw is to find some additional information, the so-called a trap.



Vazirani and colleagues want to use such functions to not only force quantum computers to generate random numbers, but also to verify that quantum computers actually work according to quantum laws - which is necessary to build confidence in random sequences.



The protocol begins with a quantum computer placing n qubits in a superposition of all n-bit strings. Then the classic computer sends a description of the quantum contour, determining the function to be applied to the superposition - the trap function without claws. A quantum computer implements a circuit without knowing anything about the trap.



At this stage, the quantum computer enters a state in which one set of its qubits is in a superposition of all n-bit strings, and the other contains the result of applying the function to this superposition. Two sets of qubits are entangled with each other.



A quantum computer measuring a second set of qubits randomly collapses a superposition into a certain result z. The first set of qubits collapses into a similar superposition of two n-bit strings, x and y, since any of them can serve as an input for a function issuing z.



A classic computer receives an output value of z, and then does one of two things. In most cases, he asks the quantum computer to measure the remaining qubits. This collapses the superposition at x or at y, with a 50% chance. This is equivalent to randomly getting 0 or 1.



Sometimes, in order to test a quantum computer for quantum, a classic computer asks for a special measurement. The measurement and its result are designed so that a classic computer with the help of a trap that only he has access to can ensure that the device responding to his requests is truly quantum. Vazirani and colleagues showed that if the device gives the correct answer to a particular dimension without using the collapse of qubits, it will be equivalent to finding a claw without a trap. And this is impossible. Therefore, at least one qubit should collapse in the device (giving 0 or 1 randomly). “The protocol creates a tested qubit inside a quantum computer that we don’t trust,” said Vazirani.



This tested qubit gives one truly random bit of information for each survey; a sequence of such queries can be used to create long random strings.



This scheme may work faster than the Aaronson protocol, but it has a clear flaw. “With a qubit count of 50 or 70, it will not be practical,” Aaronson said.



Aaronson is waiting for the appearance of the system from Google. “Whether the quality of what they show us will be sufficient to really achieve quantum superiority is a big question,” he said.



If the company succeeds, then the guaranteed quantum randomness is already at our doorstep. “We think that this will be a useful and promising market, and this is what we would like to offer people,” Martinis said.