Edward Farhi, The Physicist Behind QAOA

Edward Farhi invented two of the most-studied algorithms in quantum computing, both aimed at the same target, optimisation, which is also the application the industry most often promises. He built the quantum adiabatic algorithm in 2000 and the quantum approximate optimisation algorithm, QAOA, in 2014, and between them they have shaped how the field thinks about solving hard combinatorial problems.

What makes Farhi the right person to profile is not just that he built these tools, but that he has been among the clearest voices on their limits. He came to quantum computing after a full career in particle physics, and he brought with him a physicist’s insistence on knowing exactly what has been proved and what has merely been hoped. On the question the whole field turns on, whether quantum optimisation actually beats the best classical methods, the inventor of the leading algorithm is notably careful.

Harvard under Georgi, then SLAC, CERN and MIT

Edward Henry Farhi was born on 26 June 1952 and took his doctorate in physics at Harvard in 1978 under Howard Georgi, one of the architects of grand unified theories. He held staff positions at the Stanford Linear Accelerator Center and at CERN before joining the MIT physics faculty in 1982, where he became the Cecil and Ida Green Professor of Physics and directed the Center for Theoretical Physics from 2004 to 2016.

His MIT faculty page for Edward Farhi lists him as Cecil and Ida Green Professor of Physics, Emeritus, for the years 1982 to 2018, and records that since retiring from the faculty in 2018 he has been a full-time researcher at Google working on quantum computing. That is an unusually clean two-act career, decades as a theoretical particle physicist followed by a second life as one of the most influential designers of quantum algorithms, and the two acts are more connected than they first appear.

The particle physics half

Long before quantum computing, Edward Farhi made his name in particle physics, and his early work is still in daily use. As a graduate student he introduced thrust as a QCD observable, a variable that measures how strongly the debris of a high-energy particle collision is collimated into narrow jets. The quantity itself had been floated earlier, but his 1977 work established it as the standard way to describe jet structure. It remains a standard tool at the Large Hadron Collider decades later.

He went on to a run of influential theoretical work. With Leonard Susskind he developed the Farhi-Susskind technicolor model, an attempt to explain the origin of particle masses through new strong dynamics rather than a fundamental Higgs field. With Robert Jaffe he worked out properties of strange matter, a hypothetical ultra-dense form of matter, and with collaborators he studied the strange stars it might form.

The thread running through all of it is a knack for finding the one clean quantity or mechanism that makes an intractable problem calculable. That is exactly the skill he later brought to quantum algorithms, and it is why the two halves of his career rhyme.

Switching to quantum computing

By the late 1990s Edward Farhi had turned his attention to the theory of quantum computation, then a young field energised by Peter Shor’s factoring algorithm. Rather than work on the gate-model algorithms that dominated at the time, he asked a different question, whether the natural tendency of a physical system to settle into its lowest-energy state could be used as a computer.

This was a physicist’s instinct applied to a computer-science problem, and it produced a genuinely new model of computation. It also set the pattern for his quantum work, which consistently starts from the physics of how a quantum system evolves rather than from the abstract circuit picture.

The quantum adiabatic algorithm

In 2000, with Jeffrey Goldstone, Sam Gutmann and Michael Sipser, Edward Farhi introduced quantum computation by adiabatic evolution. The idea rests on the adiabatic theorem, a result from the early days of quantum mechanics which says that a system kept in its lowest-energy state will remain there if the forces acting on it change slowly enough.

The algorithm turns that theorem into a computer. You begin with a simple system whose lowest-energy state is easy to prepare, then slowly deform it into a system whose lowest-energy state encodes the answer to your problem. If the deformation is slow enough, the system stays in its lowest-energy state throughout, and measuring it at the end reveals the solution. The computation is the slow morphing of one energy landscape into another.

It is a strikingly different way to compute, with no gates and no circuit in the usual sense, just continuous physical evolution. It is also closely related to quantum annealing, the approach D-Wave’s hardware uses, though the two differ in important details about what is guaranteed.

Pointing the adiabatic algorithm at NP-complete instances

The following year, in a paper in Science with Goldstone, Gutmann, Joshua Lapan, Andrew Lundgren and Daniel Preda, Farhi applied the adiabatic algorithm to randomly generated instances of an NP-complete problem, the class of problems widely believed to be intractable for classical computers. For the small instances they could simulate, the algorithm performed encouragingly.

This is where care is needed, and where Farhi has consistently supplied it. Encouraging behaviour on small simulated instances is not proof of a speedup on large ones, because the trend can reverse at sizes too big to simulate. The 2001 result was a promising signal, not a demonstration, and the honest phrasing of what it did and did not show has been characteristic of his work throughout.

Why the energy gap decides everything

The adiabatic algorithm has a single point of failure, and understanding it explains much of what followed. How slowly you must deform the system depends on the smallest energy gap between the lowest-energy state and the next one up, at any point during the evolution. A large gap lets you go fast, and a small gap forces you to crawl.

For hard problems this gap can shrink exponentially as the problem grows, and when it does the required runtime grows exponentially with it, wiping out any speedup. Whether the gap stays manageable for interesting problems is the central open question of adiabatic computation, and it is genuinely hard to answer because it depends on details invisible to small-scale simulation.

Farhi’s group spent years mapping exactly where this goes wrong, studying the specific structures that cause gaps to close. That work is less celebrated than the original algorithm and is arguably more valuable, because knowing when a method fails is what lets you trust it when it does not.

The game tree result

Not all of Farhi’s quantum work is about optimisation. In 2007, again with Goldstone and Gutmann, he used a quantum walk, the quantum analogue of a random walk, to show that a quantum computer can evaluate certain game trees faster than any classical computer. In plain terms, it can work out who wins a suitable two-player game with fewer queries than a classical machine needs.

The result matters because it is a clean, provable quantum speedup for a natural problem, of the kind that is rarer than the excitement around the field suggests. It also showed the range of his approach, since the same physicist’s instinct for continuous quantum evolution produced both an optimisation method and a game-solving one.

QAOA, the near-term algorithm

By the early 2010s it was clear to Edward Farhi that the large, stable machines the adiabatic algorithm ideally wanted were far off, while smaller noisy gate-model machines were arriving. In 2014 Farhi, Goldstone and Gutmann introduced the quantum approximate optimisation algorithm, QAOA, designed for exactly those near-term devices.

QAOA has been extraordinarily influential, with more than three thousand seven hundred citations recorded on the INSPIRE literature database, and it has been run on essentially every quantum hardware platform in existence. It became the default algorithm for anyone wanting to attempt optimisation on a real quantum computer, largely because its shallowest version is simple enough to actually fit on today’s noisy machines.

The adiabatic algorithm chopped into a few layers

QAOA is best understood as the adiabatic algorithm chopped into a few discrete steps. Instead of a smooth continuous evolution, it applies a small number of alternating layers, one encoding the problem and one mixing the possibilities, each controlled by an angle. A classical optimiser then tunes those angles to push the quantum state toward good solutions.

The number of layers, written p, is the key dial. At p equal to one the circuit is shallow enough for current hardware, and as p increases QAOA approximates the smooth adiabatic evolution ever more closely, at the cost of a deeper circuit. It is a hybrid algorithm, part quantum and part classical, in the same family as the variational methods used across near-term quantum algorithms.

What QAOA has and has not beaten

The central question is whether QAOA actually beats the best classical algorithms. The honest answer is a carefully qualified one, and much of the qualification comes from work Farhi himself has helped produce.

Two findings sharpen the picture, and both come partly from Farhi’s own circle. At shallow depth QAOA can be matched or beaten by good classical heuristics, so a shallow-circuit advantage is hard to claim. And there are problem families where QAOA provably fails to reach good approximations at low depth, a limit Farhi and collaborators helped identify. The inventor documenting the failure modes of his own algorithm is the discipline the field needs.

Farhi's own group proved QAOA needs the whole graph

The single sharpest result on QAOA’s limits came from Farhi’s own group. In 2020, with David Gamarnik and Sam Gutmann, he proved a fundamental constraint that has become known by the title of the two papers it appeared in, that QAOA needs to see the whole graph. The pair covered the typical case and worst-case examples respectively.

The point is about locality. A QAOA circuit of depth p can only let each qubit be influenced by the parts of the problem within p steps of it, so at shallow depth the algorithm effectively looks only at a local neighbourhood of each variable rather than the whole problem. On large sparse problems, such as random graphs of bounded degree, this local view is provably not enough, and low-depth QAOA cannot outperform good classical algorithms on them because it literally cannot see enough of the problem at once.

It is hard to overstate how unusual this is as a piece of scientific conduct. The person who invented an algorithm, and who has every professional incentive for it to succeed, published a rigorous proof of a regime where it fails. That is the behaviour that keeps a field honest, and it is why Farhi’s assessments of quantum optimisation carry the weight they do.

QAOA and quantum supremacy

Farhi also connected QAOA to the question of quantum supremacy, the demonstration that a quantum computer can do something no classical computer feasibly can. In 2016 he and Aram Harrow argued that even shallow QAOA circuits produce output distributions that are hard for classical computers to sample from, which would be a form of quantum advantage.

The distinction here is subtle and important. Being hard to simulate classically is not the same as being useful, and a machine can display a sampling-based advantage while offering no better answers to an optimisation problem than a laptop. Keeping those two ideas separate, computational hardness on one hand and practical usefulness on the other, is exactly the kind of precision Farhi brings, and exactly what marketing tends to blur.

The move to Google

When Edward Farhi retired from MIT in 2018 he did not retire from research, moving to Google’s quantum computing effort as a full-time researcher. The move placed the inventor of QAOA alongside one of the largest experimental quantum programmes in the world, where his algorithms could be tested on real hardware rather than only analysed on paper.

It is a fitting arrangement. Farhi has always worked at the boundary between what the physics permits and what a machine can actually do, and Google Quantum AI is one of the few places where both sides of that boundary are being pushed at once. His continued presence there, still probing where his own algorithms help and where they do not, is the through line of his whole quantum career.

How to read a Farhi result

There is a consistent style to how Farhi presents his work, and learning to read it is useful well beyond his own papers. He states precisely what class of problem is involved, precisely what has been proved, and precisely what has only been observed on cases small enough to simulate, and he does not let the three blur together.

When he shows an algorithm working, he is careful to say on what size of instance and whether the behaviour is guaranteed to continue. When he cannot prove something, he says so rather than implying it. And when a result is about the difficulty of simulating an output rather than the quality of an answer, he keeps that distinction sharp, because conflating the two is one of the most common ways quantum claims mislead.

Reading quantum computing coverage with those same three questions in mind, what class of problem, what is proved versus observed, and hardness versus usefulness, filters out most of the overstatement in the field. It is a discipline Farhi models paper after paper, and it transfers directly to assessing anyone else’s claims.

The inventor as critic

The reason Edward Farhi belongs in any serious account of quantum computing is not just that he built two of its most important algorithms. It is the posture he brings to them, which is the opposite of the promotional. He builds a tool, then turns the full force of his analysis on the question of whether it actually works, and he reports the answer plainly even when it is disappointing.

That matters enormously in quantum optimisation, which is among the most over-promised corners of the field. Optimisation problems are everywhere in industry, so a genuine quantum advantage there would be worth a great deal, and that commercial pull produces a steady stream of overstated claims. Having the inventor of the leading algorithm act as its most careful critic is a powerful corrective.

The broader lesson for reading quantum computing claims is Farhi’s own method. Separate what has been proved from what has been observed on small examples, separate hardness from usefulness, and ask always what the best classical method actually achieves before celebrating a quantum one. Those habits are why his work has aged well while flashier claims have not.

The career details in this profile come from Farhi’s MIT faculty page and from his INSPIRE author record, which lists his doctoral supervision by Howard Georgi and his posts at Harvard, SLAC, CERN and MIT. The papers referenced are linked at the point they are discussed.

The algorithm in steps, without the mathematics

The algorithm this profile centres on is described in coverage more often than it is explained, and the structure is simple enough to set out. You begin with a problem whose solutions can be scored, encode it so that each possible answer corresponds to a state of the qubits, and arrange for good answers to have lower energy than bad ones.

The machine then alternates between two operations. One applies a phase to each state according to how good its answer is, and the other mixes the states so that amplitude can flow between them. Doing that pair once and measuring gives something barely better than guessing. Doing it repeatedly, with the strength of each operation tuned, concentrates the amplitude on better answers.

Those strengths are the parameters, and they are chosen by a classical optimiser sitting outside the quantum machine. It proposes values, the quantum computer runs the circuit and reports the average quality of the answers, and the optimiser adjusts and tries again. The quantum device is a subroutine inside a classical optimisation loop rather than the whole algorithm.

Understanding the shape explains both the appeal of what Edward Farhi proposed and the difficulty that followed. The circuits are shallow, which suits noisy hardware, and there is no proof that the approach beats classical methods at any depth anyone can currently run. It was designed to be tried rather than proved, which is an unusual and honest position for an algorithm to occupy.

Why the parameters turned out to be the hard part

The obstacle that emerged in practice with what Edward Farhi proposed was not the quantum hardware but the classical optimiser, which surprised most people working on it. Finding good parameters is itself an optimisation problem, and it turns out to be a difficult one, sitting inside an algorithm designed to solve difficult optimisation problems.

Two effects make it hard. The landscape the optimiser searches is full of local optima, so it settles somewhere mediocre and stops. Worse, for many circuit families the landscape becomes almost flat as the number of qubits grows, a phenomenon known as a barren plateau, which means the optimiser receives almost no signal about which direction to move.

Noise compounds it. Every evaluation of the objective is an average over many runs of a noisy machine, so the optimiser is reading a signal with error bars, and distinguishing a small genuine improvement from statistical fluctuation costs more runs. The measurement budget becomes a real constraint rather than an accounting detail.

Much of the research following Edward Farhi’s proposal has been about avoiding this rather than solving it, by choosing parameters analytically, warm-starting from a classical solution or restricting the circuit family to shapes known not to flatten. That the field spent years on the classical half of a quantum algorithm is the most instructive fact about the whole variational approach.

Frequently asked questions