Quantum Computing's dirty little secret
The problem of near-term quantum computing is not one of bad devices but bad algorithms.
Part One: The embroilment
Around 2013, quantum computing was born anew. Word around town was that there was a new paradigm for getting value out of new term quantum computers. Yes quantum phase estimation was ultimately the way to estimate eigenvalues for a Hamiltonian but we had a found a shortcut. It turns out one could simply1 apply parametrized gates to create parametrized wave function which could be used as a trial state for the true ground state of your Hamiltonian. This was wonderful because the variational principle guaranteed that the energy could only be greater or equal to the true energy so that the fear of getting unphysical wave functions was removed. The idea was brilliant; by simply using a classical optimizer which got as an input the cost function (current expectation value of the wave function) one could find new parameters for which one could hopefully find a lower value for the cost function. This is the famous Variational Quantum Eigensolver (VQE). The same basic idea was applied to the field of optimazation with the so called Quantum Approximate Optimization Algorithm .
I remember seeing these algorithms as a graduate student at University of Georgia and being invigorated by the idea that there was another world in which the complicated art of algorithmic development and analysis could simply be reduced to designing these bespoke quantum circuits (applying the right structure of parameterized gates and two qubit gates). Something though about the whole game left a sour after taste: this whole game reminded me of machine learning where I observed a lot of people mindlessly training different architectures of neural networks and treating implemented algorithms as black box oracles.
The general idea behind these hybrid quantum/classical algorithms is straightforward: encode the problem in the ground state of a Hamiltonian, design a trial wave function, select a suitable optimizer, and iteratively run the hybrid loop until the loss function decreases. Now what was the governing principle of why you would do this in the first place was never obvious but hope springs eternal.
Partly influenced by my advisor I decided that the more fruitful path for me to follow would be to figure out how to make these near-term quantum devices reliable. This became my focus as I began working at Zapata Computing. Since I used superconducting qubits, I quickly became obsessed with measurement errors (is the 0 bit you saw really what was the measurement outcome ?) and in general Error Mitigation. Error mitigation 2 is bastardized form of quantum error correction that scales very poorly with problem size and therefore cannot, in principle, replace full quantum error correction. Yet, hope springs eternal. My job as far as I was concerned was trying to get a predictable and reproducible results out of near-term quantum computers. Algorithmic development would be for others to do and I would provide them the software to run.
By mid-2021 I realized something troubling: I had not been reading any papers on these so called near-term quantum/classical algorithms. At Zapata we had weekly science meetings so I was aware of what was being done but I had began to ignore a lot of papers. I found myself focusing on the complexities of the physics of near-term devices, what quantum errors there were, how to model them, how they changed with time and how to benchmark devices and later on developed a team around these interests. But when I saw a paper on the arxiv on variatonal this and variational that, I mouthed a sigh and went to the next paper.
It began to bother me a lot that what I had began to consider a digression in the path to building a fault tolerant quantum computer was presented to the public almost as an end itself. We were supposedly going to be contributing in the not too distance future, solutions to big problems like climate change and drug discovery I saw presentations of a lot of C-Suite people and I kept asking myself what algorithm do they have in mind? The following realization occured to me around 2022:
I would not use any of the hybrid quantum/classical algorithms on a fault tolerant quantum computer let a lone on an uncorrected 60-qubit quantum device.
In 2024 I lost my first life, Zapata computing which had attempted a transmogrification into a classical artificial intelligence company was shut down. I started the day with a job and ended it without one panickingly applying to different jobs, polishing up my resume and talking to different people. The first and clear place to look was other companies doing quantum computing. Strangely enough, despite my strong desire to find gainful employment I did not really put in that much effort in finding jobs at quantum hardware companies around and was far more interested in finding out how seriously they were taking quantum error correction. The reason being that I had been convinced ,looking at the literature and my own work, that the only path to quantum advantage was through fault tolerance. What surprised me was how often this was an unwelcome conversation. In one interview, I was explicitly told that a precursor to being considered for the position was the belief in the hope of near-term quantum advantage in another interview I made it clear that I thought a vast majority of people were battling a lost cause.
This article aims to explain that the a simple conclusion: the challenges of near-term quantum computing stem not from the inadequacy of the devices, but from the shortcomings of the algorithms—a dirty little secret that needs to be openly addressed.
Part Two: Bad algorithms can’t be a basis for an economic revolution.
From this point on nothing I will say is original and I suspect controversial but it has become a common courtesy not state these ideas pellucidly. There is no reason variational quantum/classical algorithms will work and in fact we have been building evidence that they are in fact bad heuristics. I will try to summarize as best as I can the findings relating to VQE, (Variational) Quantum Machine Learning, Variational Linear Quantum Solvers and training variational quantum circuits in general. I will not give all the references but enough to make my point.
VQE
First a preliminary troubling thought about VQE: if VQE is going to be useful on a near-term quantum device with industrial-scale applications why isn’t it used as a useful quantum-inspired classical algorithm on classical devices ? No really !! Now you could dismiss this by arguing that the point of VQE on near-term quantum devices is that we can easily do cost function evaluation in a Hilbert space that we couldn’t do on a classical device and that is the point, but why aren’t theoretical computational chemists or condensed matter physicists using VQE for a problem size that let’s say fits into a 30 qubit dimensional Hilbert space. As far as I know it has never been articulated why an algorithm that is not state of the art for the working physicist or chemist should suddenly be routine on a noisy 50 qubit device. There are three reasons why I think this is the case that go to the heart of the algorithm
For quantum chemistry calculations on industrial scale molecules where accuracy is paramount classical sampling involved in VQE is prohibitively slow3 . The first detailed benchmarking approximated that one cost function for some important molecules could take on the order of days.
The requirement of initial state overlap with the true ground state for VQE is far too stringent. This is will be true in most quantum chemistry applications where the energy gap between ground state and first excited state can be much bigger than chemical accuracy. If I need a .95 overlap with the true ground state in order to find the ground state energy for a problem for which I have no clue what the ground state looks like, then it seems to me that VQE is a non-starter. To be fair, there have been suggestion to improved ground state overlap 4 5 . But then it’s not clear how near-term VQE then is as these involve vastly increasing the depth of the quantum circuits.
In the presence of noise, VQE becomes a biased estimator of the true energy and there is no sense of robustness in VQE that mitigates this problem. I will shameless promote work 6 with my collaborators that show that at least in principle (with a simple noise model) on can still have an unbiased estimator for other algorithms. This is by no means the only piece of work showing this idea7 .
So in summary, on a 50 qubit noisy device VQE is a slow and biased subroutine with high accuracy requirements. It’s important to note that the first two reasons I presented would still be true on a fault tolerant quantum computer. The idea that VQE is tied to short depth circuits on near-term quantum devices and the problem is that we need better near-term devices is besides the point. The problem is the algorithm itself and improvements that people wait for on the quantum hardware will not bring any reprieve.
Variational Quantum Linear Solvers
You probably hear about Quantum computers helping with climate change or some other far fetched thing. As far as I can tell this hope comes from being able to solve differential equations on a quantum computer. First of all the equation are non-linear and so some linearization process must be implemented after which the linear differential equation can be formulated purely in terms of a matrix inversion problem. So the hope of near-term quantum computers being helpful is that the variational paradigm can be used to solve a matrix inversion problem. Are we off to the races ? Not so quick. These quantum variational heuristics come with no guarantee as to the amount of calls one needs to the quantum computer and so some kind of quantum state verification process is mandatory. The complexity of this verification process has been investigated 8 and the cost can grow like the fourth power of the condition number. Keeping in mind that condition number can be very huge for practical applications then one must approach these schemes with much caution. Again nothing to do with hardware, just the algorithm.
Variational Quantum Machine Learning
This subfield in my humble opinion is a mess. Very early on I stopped reading any of the papers from this field. The main reason was the difficulty in trying to train these models for myself and then beginning to suspect and observe publication bias. This bias is not out of any malice or self interest but as a consequence of the incentive structures within the quantum computing community which is largely still academic. Lots of problems which will have no legs in the end are nevertheless published simply because they are novel or because the paper is presented as a “proof of concept” result; this magical phrase “proof of concept” allows ultimately unviable techniques to be published. A more systematic analysis of the literature was done here9 with the more or less the conclusion that a lot more work has to be done in actually validating any of the claims of quantum advantage. For example in some models, removing the quantum entanglement made the quantum machine learning model more effective (quantum speed ups are by the way more subtle than using entanglement). One of the leaders in the field Maria Schuld proposed tempering down the language of quantum speed ups10 .
Something is rotten in Denmark: The pitfalls of the variational quantum ansatz.
But at the heart of the variational paradigm is the claim of being able to train the quantum circuits in the first place. Here it is not easy to fail to notice the proliferation of no go results or discovery of obstacles to train with no good solution. The first result which is by now well know is the famous barren plateau problem11 . What this effectively showed is that randomly initialized parameters for a quantum circuit would on average give you gradients that are vanishingly small. This immediately called for better ways to initialize a variational quantum circuit with the inevitable counter argument being, “Well I would not just randomly initialize my quantum circuit, I would use the structure of my problem”. Now of course what this means in practise is not immediately obvious; one path is to use certain symmetries that appear in your problem. Thus arose a slew of papers where researchers provided circuits that preserved certain symmetries. A not totally un forseen outcome was that in some cases these symmetries can be exploited to get good classical algorithms12 13 .
A good summary of results on barren plateaus is here14 the main message being that the original motivation for using Quantum computers namely the exponentially large Hilbert spaces is a reliable culprit for flat landscapes that make training hard. Taking this lesson to heart one could then hopefully do the training in some low dimensional space but then again one needs to be careful that model does not became classically simulable again15. A good place to see a summary and a unified framework of training results is here.
Part Three: A coda
At the heart of all this lies a naive belief that is never explicitly stated or formulated but serves as a forcing function for our desires and boundless hopes:
Quantum Entanglement can’t make things worse, our only goal is to find where it makes things better.
I of course do not know how to find quantum algorithms but what I do know is that it’s a lot more complicated than using quantum entanglement. Quantum entanglement is a chimera; its presence can make things worse and introduce new problems or set the stage for beautiful things.
As far as I know, after three decades of research, there has only been three reasons why you would build a quantum computer:
Factoring huge numbers
Simulating quantum systems
Learning quantum states
Currently it’s my belief that our world and the agents living with all their desires and concerns are unfortunately too classical. The irony from the point of view of quantum physics is that its discovery helped bring about a revolutions in classical computing. I am hopeful though that as we continue to harness the power of quantum mechanics the need to understand it in various contexts will bring about the need for quantum computers in a self justifying and not artificial way. Our world is at its very foundations quantum mechanical, I find it implausible that a quantum computer has no place in it. But until then, you are probably wasting your time putting a vector of angles into Nelder Mead, BFGS or <insert your super amazing classical optimizer> … sorry.