Math may have caught up with Google’s quantum-supremacy claims
Math may have caught up with Google’s quantum-supremacy claims

            
  
  
  
    

    

    
      But, given the rapidly evolving quantum computing landscape, that may not matter.
    

    

    
            
              
            
    
    
      Google's Sycamore processor.

              
          Credit:

                      
          
          Google

                      
                  
          
  
          

    
    
    
      Google's Sycamore processor.

              
          Credit:

                      
          
          Google

                      
                  
          
  
  



  

  
      
    
    
                      
                      
          
In 2019, word filtered out that a quantum computer built by Google had performed calculations that the company claimed would be effectively impossible to replicate on supercomputing hardware. That turned out to not be entirely correct, since Google had neglected to consider the storage available to supercomputers; if that were included, the quantum computer's lead shrank to just a matter of days.
Adding just a handful of additional qubits, however, would re-establish the quantum computer's vast lead. Recently, however, a draft manuscript was placed on the arXiv that points out a critical fact: Google's claims relied on comparisons to a very specific approach to performing the calculation on standard computing hardware. There are other ways to perform the calculation, and the paper suggests one of those would allow a supercomputer to actually pull ahead of its quantum competitor.
More than one road to random
The calculation Google performed was specifically designed to be difficult to simulate on a normal computer. It set the 54 qubits of its Sycamore processor in a random state, then let quantum interference among neighboring qubits influence how the system evolves over time. After a short interval, the hardware started repeatedly measuring the state of the qubits. Each individual measurement produced a string of random bits, making Sycamore into a very expensive random-number generator. But if enough measurements are made, certain patterns generated by the quantum interference become apparent.
Because the rules of this quantum interference are understood, it's also possible to calculate the patterns we should see in the random numbers generated by Sycamore. But doing those calculations is very computationally expensive and gets more expensive with each additional qubit in the system. Google estimated that it would take an unrealistically long time to perform these calculations on the world's most advanced supercomputers.

          
                      
                  
                    
        
          
    
    
          
          
The one flaw with this argument that was pointed out early in the process was that Google neglected to consider the storage attached to the world's then-largest supercomputer, which would significantly cut into Sycamore's lead. But the reality remained that these computations were very difficult for classical computing hardware.
The new manuscript focuses on a key aspect of that phrase: these computations. Google chose a very specific method of computing the expected behavior of its processor, but there are other ways of doing equivalent computations. Over the intervening time, a few options have been explored that do perform better. Now, Feng Pan, Keyang Chen, and Pan Zhang are describing a specific method that allows a GPU-based cluster to produce an equivalent output in only 15 hours. Run it on a leading supercomputer, and they estimate that it would outperform the Sycamore quantum processor.
Some light-on-math descriptions
There are several ways to look at what Pan, Chen, and Zhang accomplished. We'll try three of them, getting progressively deeper into the math as we go along.
The simplest way of viewing this is in terms of the output that Sycamore provided. Individual measurements of the state of the qubits in the Sycamore processor produced a string of truly random ones and zeros, but patterns would become apparent if you ran enough measurements of a single initial state of the processor. If you set up a classical calculation that recapitulates the physics of Sycamore, you would get the same level of randomness and the same patterns.
What the new paper describes is a way to trade off some of the fidelity of the calculated reconstruction of the processor's behavior but gain much faster calculations in the process. In other words, the new calculations don't exactly recapitulate the behavior of Sycamore, but they still produce the patterns and the underlying randomness, and they can be completed much faster.

          
                  
                    
        
          
    
    
          
          
That's explanation one. Option No. 2 for understanding this involves considering how the starting state of the Sycamore processor evolves into its state at the point of measurement. Multiple possible paths will get there and, this being a quantum system, it explores all of them. To get an exact model of the Sycamore processor's output, you'd also have to explore all the paths, which is very computationally intensive. Pan, Chen, and Zhang found a means of limiting the paths you look at that makes the calculations tractable while still achieving an equivalent output.
Those of you who want to avoid math should now skip to the next section header. The actual calculation method describes the interactions of Sycamore's qubits as a three-dimensional tensor network, with the tensors dictating the relationships among the properties of the qubits. The algorithm then simplifies this down by severing some of the network's connections—the researchers describe this as doing the equivalent of drilling three-dimensional holes through the network.
Each hole you drill cuts the fidelity of its calculations in half. But that makes the fidelity completely adjustable: you can ensure you have a sufficient recapitulation of Sycamore's behavior simply by limiting the number of holes you drill. The mathematics of where those holes were drilled within the network were dictated by the physical structure of the Sycamore chip itself.
The resulting contracted tensor network was significantly easier to model, although the researchers had to split it into subtasks that could be stored on the system they were working on. And they used their algorithm to model the behavior of smaller qubit networks on Sycamore and showed that it produced results that were accurate within their fidelity limit.

OK, done with the math now
However you want to view it, the calculations were far more tractable. A cluster of 512 NVIDIA Tesla V100s needed only 15 hours to model the behavior of the full Sycamore chip. And the researchers note they haven't even started to optimize their procedure yet—the tensor contraction step was set up so that it could be implemented simply using an existing Python library, and they think more specialized software would do better.

          
                  
                    
        
          
    
    

        
        
          
          
Scaling up from their GPUs to a supercomputer, the researchers estimate that it would take less time to do this than was needed for Sycamore to accumulate enough measurements to detect the pattern of quantum interference. In other words, claims of quantum supremacy appear to have been premature.
If this sort of thing sounds vaguely familiar, that may be because something similar happened with D-Wave's quantum annealer. Early on in the company's history, D-Wave would sometimes announce that its annealer had outperformed the best existing algorithms for a specific problem. But the computer science community often viewed this as a challenge, upped its game, and came away with a new algorithm that outperformed the quantum hardware. The company has since become more circumspect with its claims.
At the same time, the manuscript was made somewhat out-of-date within weeks of its appearance, as IBM announced that it had a new quantum processor that was more than double the size of Google's Sycamore. Even with a more computationally tractable algorithm, the behavior of IBM's Eagle processor will be vastly more difficult to model. It's fair to say that, should an equivalent calculation be performed on Eagle, the quantum hardware would almost certainly retake the lead.
But that calculation seems unlikely to get done by IBM. In our chat with Darío Gil, head of IBM research, he dismissed the idea of quantum supremacy and instead focused on getting to what he termed quantum advantage: where quantum computers consistently outperform classical ones on problems that are useful for companies. So, unless someone else wants to pay IBM to reserve the time needed to perform Google's computations on IBM's hardware, this is likely to get fairly academic.
The arXiv. Abstract number: 2111.03011  (About the arXiv).


          
                  

                  
          


  




  
  
          
  

  
    

    
      John is Ars Technica's science editor. He has a Bachelor of Arts in Biochemistry from Columbia University, and a Ph.D. in Molecular and Cell Biology from the University of California, Berkeley. When physically separated from his keyboard, he tends to seek out a bicycle, or a scenic location for communing with his hiking boots.

    
  



  
    
    
    75 Comments
  
      





  
              
  


  
    
      
      
    
    
              
                      
              
            
                    
        
                    
                    
        
                    
                    
        
                    
                    
        
                    
                    
        
                  



  

  