Last week, there were a number of reports on Google having achieved quantum supremacy (e.g, see Rumors hint of Google achieving quantum supremacy ScienceNews). The technical article behind the reports was taken down shortly after having appeared. Unclear why but some of their quantum computing rivals have declared this as a true breakthrough to just a publicity stunt.
Using BING, I was able to find an (almost readable) copy of the paper on FileBin and cached copy on SpaceRef.
What Google seems to have done is to implement in a new quantum processor, a (pseudo) random number generator, a random sampling algorithm and an algorithm that verifies randomness based on the sample. he pseudo-random number generator was a quantum circuit, and the sampling another quantum circuit. Randomness verification was done by computing the probability of a bit string (random number) appearing in a random number sequence sample and then verifying that that bit string did appear that often. This is a simple problem for classical computers to solve for a few random numbers but get’s increasingly hard the more random numbers you throw at it.
What is quantum supremacy?
Essentially, quantum supremacy states that a quantum computer can perform a function much faster than a standard digital computer. By much faster we are talking many orders of magnitude faster. The articles noted above state that the Google Quantum computer did the algorithm in minutes, that would take 1M cores, 10,000 years to perform on digital processors.
Quantum supremacy applies an algorithm at a time. There’s a class of problems that are considered NP (non-deterministic polynomial [time]) complete which can only be solved on classical, digital computers using brute force algorithms (e.g., algorithms that check every possible path) which can take forever for many path problem spaces (see NP-completeness, wikipedia)
Quantum computing, because of it’s inherent quantum ness characteristics, should be able to test every path of an NP complete problem in parallel. As a result a quantum processor should be able to solve any NP complete problem in a single pass.
Quantum supremacy simply states that such a quantum computer and algorithm have been implemented to solve an NP complete problem. The articles say that Google has created a quantum computer and algorithm to do just that.
Google’s Sycamore quantum computer
Google’s research was based on a new quantum computing chip, called the Sycamore processor, which supports a two dimensional array of 54 (transmon) qubits, where each qubit is “tunably” coupled to its nearest 4 neighbors. In the figure the “A” qubit can be coupled to it’s 4 nearest neighbor ‘a” qubits via tuning. 1 qubit failed, leaving 53 qubits for the computation.
The system is cooled to reduce noise and to enable super conductivity. The qubits are written by two mechanisms, a microwave drive to excite the qubit and a magnetic flux inducer to control its frequency. Qubits are read via a linear resonator which is connected to each qubit. All qubits can be read simultaneusly by a frequency multiplexing approach and are digitized to 8 bits @1GS/s (giga-samples/second, so 1GB/sec).
The Sycamore quantum architecture could generate 1113 single-qubit gate or 430 dual-qubit gate circuits. This inherently constrains the algorithmic complexity or problem state space that it could solve.
Qubit state, tunable couplers and quantum processor controls are written via 277 digital to analog converters in 14 bits [words] @1GS/s (or ~1.75GB/s). A single cycle of a Sycamore single-qubit circuit can be stimulated by a 25ns microwave pulse (with no qubit to qubit coupling active).
A key engineering advance of the Sycamore systems was achieving high-fidelity single- and dual-qubit operations, which means that they were completed correctly
What the Sycamore quantum computer accomplished
They generated 30M random numbers (with m=20 bits/random number) and then randomly sampled 1M of them, computed the probability of their occurrence and verified that that number was seen (within some error threshold). The random number generation, sampling and probability computation/verification took 200 seconds on the Sycamore system. They said that most of that activity was input and output and that the Sycamore quantum computer was only busy for 30 seconds working on the problem.
In comparison, the Google team benchmarked GCP processors and the Oak Ridge National Labs Summit supercomputer complex doing a portion of the algorithm using standard digital functionality and have concluded it would have taken 10K years on 1M processing cores to perform the same function using digital computers.
Although the problem to generate vast numbers of pseudo-random numbers, randomly sample them and verify they meet proper probability distributions may not be that useful, it does represent an NP-complete problem. Many NP-complete problems can be solved with the same algorithm, so there’s a good probability that similar NP complete problems may also be solvable with the Sycamore quantum computer.
1M cores for 10K years seems much too long
However, it doesn’t seem to me to take that long to generate pseudo random numbers, sample them and validate their probabilities were correct.
It took me ~1 sec to generate 10,000 (probably 32 bit but could be 64 bit) =RAND() numbers in Microsoft Excel, so 30M would take take about 15K 3K seconds on my desktop or about 4.2 hrs 50min.. Generating a random sample of 1M should take another 100 seconds (to generate another 1M random numbers), creating indexes out of these another 100 seconds or so, then accessing these 1M random numbers in the 30M random number list should take another 100 seconds (maybe) so add another 5 min to that. Verifying that the sampled numbers met all the random number probabilities it should ], is another question but here we are only dealing with 1M pseudo random numbers so it shouldn’t take that long to compute its frequency occurence and its probability to validate randomness. Yes, Excel =rand() function is probably not the best pseudo random number generator but it’s typical of what exists for digital computers and even if it took twice as long to generate better pseudo random numbers , it’s still not anywhere near 1M cores for 10K years.
But then again I’m no numerical specialist and even at 30 seconds vs 15.2K 3.3K + ? (for probability calculation + frequency verification), so multiply this by 5X or 16.5K seconds, makes the Sycamore quantum computer, ~1000X ~550Xfaster or ~2.5 orders of magnitude faster.
In my mind, Sycamore and its quantum algorithm is more of a proof of concept. The Sycamore processor proves that a) quantum computer with 53 qubits can solve some real world NP-complete problems and b) that the more qubits that quantum computing industry provides the more sophisticated NP complete problems it will be able to solve. Just not sure this is actually a 13 16 orders of magnitude speedup.
[My math was off but I tried to fix it in these last three paragraph, Ed.]
~~~~
Let’s see if a 20 bit NP complete problem can be solved in a quantum computer with 53 qubits, how many qubits should it take to solve a 256 bit NP complete problem (e.g. cracking an AES-256 bit encryption), maybe ~680 qubits. Phew, my AES encrypted data are safe, at least for the moment.
Photo Credit(s): From ScienceNews article about achieving quantum supremacy
