Raising the four words “quantum advantage” at a conference full of computer scientists, it’s likely that one person will get bored eye roll. This phrase refers to the milestone at which a quantum computer successfully performs a task that is very difficult using the computing power of classical computers. Previously, the task mentioned above had little practical value, just a test for quantum computers, so scientists showed a bored face when they heard the phrase “quantum supremacy – quantum advantage “.
But now, information from many sides shows that Google’s quantum processor is about to hit (or even gain) that quantum advantage, and it turns out we will also have a real application. fact: that is pure random generation.
“Randomness” is important in almost everything related to computing and communication infrastructure. In particular, randomness is what makes up the security of encrypted data, protecting everything from spontaneous chats between two friends to national secrets that need to be hidden.
It is very difficult to find pure randomness – for example, a series of numbers where no calculation can predict the next number. But when quantum computers really do surpass classical computers, the random factor is much different from the random values we still know. Actions used to demonstrate quantum supremacy will not only show the power of a computer, but also generate pure randomness and sufficient basis to prove it.
“We are really excited about it. Everyone expects this to be the first application of a quantum computer“, Said John Martinis, a physicist at the University of California and also lead the quantum computer research effort at Google.
“Random” and “quantum theory” go hand in hand like thunder and lightning. When the sky is lit up by “quantum theory”, no doubt a buzz of “random” will appear soon after. Scientists believe that the systems that exist in the quantum world are mostly sets of many states, often in the “superposition” state (allowing data to exist in both states. slices 0 and 1); when you take the measurement, it “collapses” down into a single state. Quantum theory allows scientists to compute the possibilities that may occur when making a measurement, and the results of the measurement are essentially pure randomness.
Physicists are still trying to apply this property to create systems of generating random numbers – most of them based on measurements of a quantum superposition state. Although for us “ordinary people”, these systems will fulfill the need to use randomness (such as sweepstakes), but operating them is not easy. Besides, it is indeed very difficult to prove that these random number generation systems are truly random. And finally, some of the ways of generating randomness (and allowing us to prove that this randomness is real) requires sophisticated machines, with many devices placed at great distances.
Recently, there are experts suggesting how to generate random from only a single device, which is a quantum computer, through a method called “sampling task” – a in the first tests to demonstrate “quantum advantage”. To understand this task, imagine yourself receiving a box containing small plastic pieces engraved on the surface with the letters 0 and 1, such as “000”, “010”, “101” and so on.
If there are only 3 characters, there are 8 types of arrangements in total. However, there may be several pieces of plastic in the box with the same number; for example there may be as many as 50 pieces labeled 010 or 25 pieces labeled 001. Distribute the pieces with different numbers to accurately indicate the rate at which you will randomly pull out any piece of plastic. In this case, the odds of you getting the 010 piece will be more than twice the rate of getting 001.
The sampling task will require a computer algorithm to do the same thing as reaching into a plastic shard box, with a given total number of pieces of plastic that will pick a random result. The higher the rate of drawing a three-letter combination, the greater the probability of the algorithm picking out that number.
Of course, the algorithm will not “grow” anywhere to pick up a piece of plastic containing the number in the box. It will randomly output a binary number, say 50 bits long, after the machine receives a categorization request specifying the desired ratio of each 50-bit output string.
With classical computers, the complexity of this task is directly proportional to the number of bits in the output string. But with quantum computers, this task is not very complicated whether the output string is 5 bits or 50 bits long, which is the power of quantum computers.
The quantum computer will start the calculation with all of the qubits – its quantum bits – in a certain state; Let’s assume this state is 0. As well as how classical computers compute classical bits using s logic gate – logic gate, quantum computers also control qubits through quantum gates.
But quantum gates can send qubits into strange states. For example, a gate can turn an input value of 0 into a superposition that includes both 0 and 1. If we compute the state of the qubit at that time, it will randomly “crash” down to one of two states. moves 0 and 1, with equal rates of occurrence.
Even more oddly, quantum gates processing two or more qubits at the same time cause the qubits to “confuse” with each other. In this case, the qubits state will be tangled and can only be described under a single quantum state.
If you combine a bunch of quantum gates, and make them work with a set of qubits in a certain sequence, you create a quantum circuit. In this example, to get a 50-bit output, you had to create a quantum circuit that puts 50 qubits together into a superposition state, capable of describing the output value distribution you want to have.
When measuring these qubits, the entire superposition state will collapse randomly into a 50-bit sequence. Each quantum circuit determines a different value distribution, these distributions will be the decisive factor for the rate for qubits to collapse into a value chain. You can compare measuring a qubit with the act of blindfolded, reaching into a box to get a piece of plastic with a number.
What do these quantum circuits have to do with random numbers? The decisive factor is this: the 50-bit sequence that the quantum computer takes out will have a very high entropy – a measure of volatility – from which we get random.
Aaronson’s principle of random generation is easy to understand: a classic computer will pick up a few random bits from some reliable source, and use these “random seeds” to generate the description. of a quantum circuit. The resulting random bits will determine the type of quantum gate and the sequence in which the qubits are processed. The classical computer sends these descriptions to a quantum computer that already has quantum circuits, which will measure the qubits and send back a sequence of 50-bit output values. In this way, the quantum computer has obtained a random sample from a different value distribution for each quantum circuit.
The next step would be continuous sampling, eg taking 10 samples with each quantum circuit. The classical computer will use statistical tests to ensure the high entropy output value chains. In the published study, in collaboration with researcher Lijie Chen, and another research still in the works, Professor Aaronson points out:
Under the well-established assumption that these mathematical problems are extremely difficult computationally, the quantum computer sample was obtained from a higher entropy value dispenser at the same time. the value must be calculated by classical computers.
Under the well-established assumption that these mathematical problems are extremely difficult computationally, the quantum computer sample was obtained from a higher entropy value dispenser at the same time. must have been calculated by classical computers.
After testing, the classical computer will put all the 50-bit outputs into a classical algorithm. “It produces an almost perfectly random long chain of values“, Professor Aaronson said.
Aaronson’s principles have the highest application value for quantum computers between 50 and 100 qubits. Once a system’s qubits exceed this threshold, the quantum computer becomes so difficult to control that classical supercomputers cannot apply the principle to work out the results. This is when we need another form of definable randomness, a way to use the power of a quantum computer.
The new approach uses a mathematical technique with a bold name: jaws “hatch without nail scratches”. According to. Umesh Vazirano, a computer professor at the University of California who developed the technique of randomness with Zvika Brakerski, Paul Christiano, Urmila Mahadev and Thomas Vidick, “its nature is much more horror than the name suggests. “.
Imagine the box containing the other distribution of value again. Instead of reaching in to get a string of values, this time you add a string of values equal to n, call it “x”, then the system will output another sequence of n bits. Somehow the box has linked an input string to an output value chain. A special possibility appears in the box: for each x, there will be another input string named y that also produces an output value string similar to x.
In other words, we have two input strings x and y, but the other box produces the same output of z. The trio x, y and z are called a “claw”, and in computer science language, the other box is a function. Calculating the function is very simple, which means that as long as x or y, z will appear. But if there are only two values x and z, finding y is impossible, even with a quantum computer.
The only way we have a complete set of claws is to have some internal information to stand from the outside, we can also calculate the results; My “inside hand” will be a trapdoor.
Vazirani and colleagues want to not only use those functions to make quantum computers generate randomness, but also to confirm that quantum computers function according to quantum mechanics theory – crucial for us. I can believe that the other result is truly random.
Vazirani’s principle comes into force when a quantum computer puts a quantity of n qubits into a superposition in a long n-bit chain. The classical computer then sends out a description of the quantum circuit to determine the computational function corresponding to the superposition state – this is the shutter function that has no scratches on the xyz nail. The quantum computer will use this function to build a circuit without knowing anything about the hatch that is plugged in.
At this stage, the quantum computer goes into a state that allows part of its qubit to enter the anti state in an n-bit sequence, while another set of qubits computes the result when applying the other function to the husband state. These two qubits will get tangled up.
The quantum computer will measure the second set of qubits, causing the superposition to collapse into a result z. The first set of qubits will collapse into a superposition state with two n-bit strings, one is x and the other is y, because either x or y can be the input value for the function to calculate z.
The classical calculator receives z output and then does one of two possibilities.
Most of the times, it will send the query request to the quantum computer to work out the remaining qubits. This will cause a stack, with a 50% chance of generating either x or y. That is, the quantum computer will randomly calculate either the value 0 or 1.
Sometimes, To test the quantum computer of a quantum computer, a classical computer would issue a special computation requirement. This measurement and its results are designed so that a classical computer, with the help of a shutter that only a classical computer has control over, can ensure that the device is answering the query. must be quantum (from which randomness asserted).
Vazirani et al. Demonstrated that if the device could answer that particular query without the collapsing qubits, it would have computed the xyz claw without the shutter. This is obviously not possible. So there must exist at least one qubit collapsing inside the device (with a random value of 0 or 1). “This principle creates an immutable qubit inside an unreliable quantum computer,” Vazirani said.
This may be faster than Aaronson’s quantum sampling rule, but there is a noticeable disadvantage: Aaronson says it cannot be effective in a 50 or 70 qubit system.
At the moment, Professor Aaronson is waiting to see if the Google system succeeds or fails to see if Google’s quantum computer truly achieves quantum advantage.
If we do, we will get very close to a quantum random generated milestone that can be demonstrated with a single quantum device. “We think this is a very useful and potential market, and then we will think about its commercialization“, physicist John Martinis said.
Refer to Quanta Magazine, Wired