Source: Deep Learning on Medium
Quantum Supremacy — Google Sycamore Processor
The holy grail of quantum computing is to demonstrate speed supremacy over the classical computer, the computer we have today. The complexity of the RSA cryptographic algorithm was thought to be exponentially grown with the length of the key. This algorithm safeguards our secure Internet transmission for decades. It was once using a 1024-bit long RSA key but extended to a 2048-bit RSA key in neutralizing faster computers. Since the complexity grows exponentially with every bit, we will be safe for a long while. In 1994, Shor demonstrated a quantum algorithm that cracks the RSA algorithm in polynomial time. Nevertheless, this remains theoretical since we don’t have a quantum computer to make it happens yet. This is why the Sycamore Processor generates so much attention. Google claims to achieve quantum supremacy with its new processor. Fortunately, it has only 53 qubits which the Shor’s Algorithm may take millions of qubits to crack the 2048-bit key!
For those new to Quantum computing, allow me to do a quick introduction.
Why is Quantum Computer supreme? (Optional)
A “bit” in the classical computer holds either 0 or 1. Many magazines contribute the quantum breakthrough on how a qubit (a quantum bit) can hold more information than a binary bit. This is very misleading.
Let’s do some simple math. Say a qubit can hold 1 billion more information than a binary bit, a 53-qubit machine is equivalent to a 6.6 GB classical computer. I purchased a 16 GB laptop 5 years ago! So this cannot be the quantum supremacy. So what is the reason?
Let’s imagine we have a 3-bit classical computer. A variable, say “a”, can be in one of the 8 states. We can reformulate the assignment a=6 in an odd way below.
In this equation, we have 2³ coefficients. But for our classical computer, only one coefficient is one and all others are zero.
Classical computer is a single-issue voter. It takes only one single position at a time.
Quantum mechanics claims that a system can be in a superposition state. If you hear about Schrödinger’s cat thought experiment, it explains that a system can be in different states at the same time. The cat can be alive and dead simultaneously. I don’t like to explain quantum mechanics this way. But mathematically, for a quantum computer, the coefficient of a 3-qubits system does not need to have exactly one value of 1 with others to be zero.
Indeed, all 8 coefficients can have any real numbers or even complex numbers. Classical computers are like a light switch that either has the light on or off. Its state is in one of the eight states only. For quantum mechanics, it does not need to be in a particular state until we measure it (observing its value).
Nature only picks a side on its state when we measure it.
So a superposition can be represented mathematically with non-zero coefficients. This is the rule of nature. Look bizarre from our experience but it is true because many possible effects are regularly masked out (cancel out) on the human scale.
We apply operations in manipulating the equation above before making a final measurement. In addition, don’t underestimate the power of exponential! A 64-qubit system contains
coefficients. The biggest US lottery jackpot was 1.6 billion dollars. 2⁶⁴ is about winning the biggest lottery 30 billion times. With 64-qubits, we can encode and manipulate a lot of data using these billion-billion coefficients. But quantum computers do not have traditional arithmetic or logical operators. In fact, it has no “if” loop or “while” loop structure. That is why you cannot recompile a C++ program and run it on a quantum computer.
So what operators quantum computers have. Quantum computers apply quantum gates to manipulate the superposition state. Conceptually, a quantum gate acts like matrix multiplication on a vector (the superposition state) in linear algebra.
In quantum mechanics, the Schrödinger equation describes how states evolve. It is a linear system. Nature is governed by quantum mechanics. That is why Richard Feynman asked
What kind of computer are we going to use to simulate physics?
For Feynman, quantum computers are the most natural way. With careful design of the basis of a system, many non-Physics problems can be solved through linear algebra. In classical computers, this vector contains exactly one value of 1 with zero otherwise. i.e. it can be in one state at a time only. This limits the expressiveness of the tool. For quantum computers, we can manipulate billions of information simultaneously with a single quantum operation.
Quantum Entanglement (optional)
But this paints a pretty naive picture. The real answer for quantum supremacy remains a mystery. While we develop new quantum algorithms, we do sometimes find corresponding classical algorithms that match the performance of quantum algorithms. That’s one reason why finding quantum supremacy is very hard and why there is so much attention on Google’s quantum supremacy claim. What we may know is that a quantum algorithm cannot be supreme than the classical method if it does not utilize quantum entanglements. The parallel manipulation on a superposition is the ingredient while quantum entanglements are the secret sauce. However, we don’t know the exact reason.
If two apples cost $2, each apple costs roughly $1. In classical systems, we believe that if we know every detail of the state of a system, we know every states of its subcomponents. That is not true in nature. In nature, a system can be in a superposition state. We can prepare states that are correlated but not with specific measured states. For example, in a system composed of 2 qubits, we can create states with a 2-qubit quantum gate that both qubits having the same measured value (or create states that are always opposite). This is as easy as creating |0 0⟩ or |11⟩. However, given two separate qubits prepared separately with any supposition values, we cannot concatenate two qubits together to reproduce the entangled state.
In a nutshell, we can prepare a composite superposition which will be measured as |00⟩ or |11⟩. But we cannot simply concatenate two separate qubits together without applying a 2-qubit operator.
In some perspective, we create a correlation pattern for the data. In classical computers, we may have to encode such information as two separate scenarios: “00” or “11”. For a k-qubit system, such a correlation pattern can be extremely complex. It has different combinations of which qubits are the same and the opposite. But yet, we don’t know enough to rephase an algorithm into an entanglement problem.
Theoretical Challenges (optional)
There are a couple of theoretical challenges in quantum computing. First, the complexity in loading values for the coefficients grows exponentially. Unless we identify data patterns in the input to load them polynomially, we are still under the curse of exponential. To find one quantum algorithm that the classical algorithm cannot match, it is even much harder. Second, we cannot directly probe the coefficient values. We find the state by measurement but the superposition will collapse. When superposition is measured, nature takes one of the measured state with probability equals to the square of the corresponding coefficient.
For example, if the answer is|010⟩, we manipulate the system to push the coefficient for |010⟩ very high. We repeat the calculation many times and sample the solution. Then, we should find that many measurements land in |010⟩.
There are other possibilities in finding a solution by finding patterns in the coefficients. But the mentioned constraints make developing supreme quantum algorithms very hard and non-obvious. In fact, we don’t have a zoo of quantum algorithms yet even with 30 years of research. But we may only need a few of them to solve some critical problems.
Google Sycamore Processor
Now, we are ready in talking about Google Sycamore Processor. It is a 53-qubit processor (one qubit out of the 54-qubits is not working). The design is based on superconducting circuits. The challenge of quantum supremacy is solving a problem far more efficient with quantum computers than classical computers. Typically, a supreme quantum algorithm would break the curse of exponential complexity into polynomial while the classical algorithm cannot. In the Google paper, it produces a sequence of pseudo-random generated streams in 200s while it is estimated to take 10,000 years with a classical computer to simulate the same result. The current IBM quantum computer (as of 10/2019) has 53 qubits. There are other quantum processors that have more qubits. So there are two possible reasons for the Google claim:
- the choice of the algorithm in demonstrating the supremacy or
- the improvement in the quantum gate fidelity.
In fact, IBM has responded with claims that the chosen algorithm can be solved by an “idea” simulation with classical computers in 2.5 days only. The reward and the competition is fierce, so does the counter-arguments. But don’t let it spoil the fun. I will focus on Google’s quantum processor here.
As recalled, Shor’s algorithm may require millions of qubits to hack the 2048-bit key. Some people may say that it can be solved with thousands of qubits. The main discrepancies are related to fault tolerance. In engineering school, we rarely talk about this topic anymore.
But matters interact.
The quantum information in qubits is very delicate. Once, we start a quantum program, we cannot pause it and take a coffee break. The quantum information degrades continuously. There are two major designs in quantum computers: superconducting circuit & trapped ions. Both are susceptible to degradation, but the superconducting circuit seems to be worse. But it usually has faster gates. Usually, the superconducting circuit has a few minutes before the game is over, i.e. the quantum information is degraded to noise. Due to the random nature of quantum mechanics, the fault tolerance topic comes back. To improve the fidelity, we can build fault tolerance circuitry to correct errors. This is why it is estimated that it takes millions of qubits to break the current RSA keys. But 53 qubits are barely enough for anything, so the improvement would be on the gate fidelity. In the superconducting circuit, it builds artificial quantum systems in the form of circuitry. Therefore, no two qubits will be identical. Quantum computers often require recalibration daily. In particular, calibration is important since we are not dealing with a digital system anymore. Google introduces a method to calibrate and benchmark the processor using the cross-entropy benchmarking.
The basic building blocks for many electrical circuits include capacitors and inductors. Below is a resonator using a capacitor and an inductor.
The qubit in a superconducting quantum computer is actually a resonator circuit with a capacitor and an inductor. But we need two quantum states that are wide apart in the quantum scale and can be manipulated easily. Google Sycamore processor utilizes the two lower quantum states in the resonator circuit.
But we don’t want the energy difference between states to be uniform. Otherwise, the energy required to raise from the state |0⟩ to |1⟩ can mistakenly raise a state from |1⟩ to |2⟩ also. The desired nonlinear energy levels are created using a Josephson junction as an inductor.
Energy dissipation degrades quantum information. That is why the chip is cooled down close to absolute zero (20 mK) in a dilution refrigerator. This creates Cooper pairs in the superconductor that have no resistance. It also reduces ambient thermal energy so it does not have enough energy for a quantum jump in the qubit. Don’t worry too much about Cooper pairs and Josephson junction. Scientists recieve Nobel prizes for that. Below is a 9-qubit processor.
Superconducting quantum computer suffers a problem that is more serious than the trapped ion. In classical computers, we can randomly load to memory into the CPU registers. And we can apply operations to any two pairs of registers op(r₁, r₂). But in superconducting quantum computers, operators can be applied to neighboring qubits only. So op(q₁, q₂) works if qubit q₂ is one of the four neighbors of q₁ in a rectangular lattice.
Both IBM and Google quantum processors use transmon qubit. It is a variant of charge qubit. Transmon prolongs the T₂ Dephasing (the degrading of the superposition) which improves from 1–2 μs in charge qubit to 100 μs. A charge qubit has basis states represent the presence or absence of excess Cooper pairs on the island. The state is determined by the number of Cooper pairs that have tunneled across the junction.
A single-qubit quantum gate in the Sycamore Processor is executed by driving 25-ns microwave pulses resonant with the qubit frequency while the qubit–qubit coupling is turned off.
For anyone who breaks the current RSA encryption first, they can claim the quantum supremacy for sure. But we are still far away from there. The choice of tasks in demonstrating supremacy remains debatable. Previously, we can show it with toy algorithms using an Oracle. This is quite unsatisfactory because these Oracles usually show no value in solving real problems. But even for those problems, no quantum computer has shown supremacy yet. Regardless of other claims, this is a significant milestone because it demonstrates a problem with some real value.
I used to have problems understanding why random generators are often referred to as pseudo-random generators. It turns out random number generation is hard. We usually approximate the process. But random generators are important for fields like cryptography, gambling or numerical simulation of physical systems. The German Nazi’s Enigma machine was hacked partially due to the fact that the messages are ended with “Heil Hitler”. This creates a pattern that can be hacked.
The task chosen by Google’s teams is a pseudo-random quantum circuit. It implements a quantum circuit of depth 20 with 430 2-qubit and 1113 1-qubit gates. The circuit entangles a set of qubits by repeated application of these quantum gates. Sampling the circuit’s output produces a set of bitstrings, like 01001101, 10111000, … These streams are pseudo-random because quantum interference will make certain bitstrings to be more likely. This is the same principle behind the double slot experiment.
To create a classical version with the same probability distribution of the bitstream output (i.e. generator similar randomness of bitstreams), it usually requires a direct numerical simulation of the quantum circuit. But the simulation complexity grows exponential in the number of qubits and the depth of the circuit. Classical computers can simulate the problem corresponding to quantum circuits with qubits in the range of 40. Beyond that, it really pushes the limit of classical computers because of the exponential state vectors that it needs to track. For IBM, it claims that if more advanced optimizations are used with disk space as a fall back for the available memory, the classical computers can theoretically solve it in 2.5 days. For this task, Google pushes the limit on the states to track in classical computers to prove the quantum supremacy. This is the strategy in identify problems that classical algorithms cannot escape the curse of exponential. But to achieve the supremacy, the gate error rate must be low since accumulated errors kill in quantum computing. The gate sequence for the pseudo-random quantum circuit generator is shown below:
Calibration is a critical part of the quantum computer operations. The cross-entropy benchmarking is a metric that related to the probability distribution of the bitstring produces by the quantum circuit and the theoretical one computed by the simulation on a classical computer. We should not worry too much about the definition below.
A value of 1 indicates an error-free circuit while 0 means it is bad. This metric can be used to calibrate and to benchmark a quantum computer. In the quantum supremacy experiment, it wants to achieve as high F value as possible for a very deep circuit with many qubits.
On each qubit, the benchmarking applies a variable number of 1-qubit quantum gate to measure F. In addition, it executes the same 1-qubit gate to all qubits simultaneously. The error difference is small so it indicates the processor has low microwave crosstalk (measuring the negative impact of one operation on other qubits).
As a reference, this is error rate for different operations.
To move forward, the number of qubits need to increase as well as the fidelity of the qubits and the quantum gates. Google Sycamore Processor focuses on the fidelity. Some people may argue that that is not a critical breakthrough. But definite, it establishes a major milestone in addressing a problem in a real quantum computer that takes far much longer (if not “forever”) to complete.
We have a couple articles detailing quantum computing as well as the superconducting quantum computer. Feel free to check it out.
If you want more technical details, the supplementary information of the research paper is definitely a good start.