One proof narrows quantum computing's reach while a Google contest tries to cut its costs

A new proof from Stony Brook University shows that on one well-studied puzzle, a quantum computer can find the answer exponentially faster than an ordinary computer but cannot efficiently show how it got there. Google Quantum AI, meanwhile, is offering $150,000 in prizes for AI-designed circuits that cut the cost of quantum algorithms already considered promising, so one story removes a task from quantum computing's list while the other tries to make listed tasks cheaper.

A third story, Japan's NEDO Quantum Challenge, shows what today's hardware is actually being used for. None of the three rests on a peer-reviewed paper yet: the Stony Brook proof, a competing proof of the same result and Google's companion paper are all arXiv preprints that have not been peer reviewed, and the NEDO winners' results are described in a vendor blog and a trade report.

A maze with an exit but no directions

The puzzle is called the welded-tree problem. Picture two branching trees whose outermost tips are joined by a tangled loop; the root of one is the entrance, the root of the other is the exit, and an algorithm can only ask, junction by junction, which passages connect where. In 2003 Andrew Childs and five colleagues showed that a quantum walk (a quantum search that spreads through the maze like a wave whose parts reinforce or cancel each other) finds the exit exponentially faster than any classical algorithm, Stony Brook's account explains.

Finding the exit is not the same as giving directions. A classical search can log its steps and trace them back, but keeping such a log disturbs the interference the quantum walk depends on. Scott Aaronson put the question of whether any quantum method could efficiently produce a route on his 2021 list of open problems. In 2023 Childs, Matthew Coudron and Amin Shiraz Gilani proved route-finding hard only for algorithms obeying two restrictions, one being that they always remember a path back to the entrance.

Graduate student David Miloschewsky and assistant professor Supartha Podder posted their preprint on 17 September 2026. It proves that for a maze whose trees have height n, any quantum algorithm needs at least on the order of 2 to the power n/24 queries (questions to the maze about a junction's neighbors) to output an entrance-to-exit route with constant probability. Five days later Joseph Carolan, Childs, Coudron and Gilani posted a separate proof with a bound of 2 to the power n/12. Stony Brook says both proofs show the task takes exponential time but not exactly how much, and that the two groups are now working together on the optimal bound.

Two details deserve attention. The Stony Brook paper notes that its query model and its random choice of mazes are similar to, but not exactly the same as, the 2003 setup. And its AI disclosure says ChatGPT found a much simpler proof for one section and an appendix and was used to discuss whether the proofs were correct, while the authors say they verified all content.

A contest to shrink error-corrected circuits

Google's announcement, posted on 21 October 2026 by Tanuj Khattar and Ryan Babbush, starts from cost. Quantum error correction (spreading information across many qubits so faults can be caught and fixed) adds overhead to every qubit and gate, so Google argues that circuit size is one of the biggest factors in when a quantum algorithm becomes practical.

The obstacle to letting AI agents redesign circuits is checking their work, because general quantum circuits cannot be efficiently verified on classical computers. Google's answer is kickmix circuits, built from reversible classical logic, phase gates and measurement-based clean-up, which map each input bit string to a single output without creating new superpositions. That lets an ordinary computer run randomized fuzz testing (throwing many random inputs at a circuit to catch mistakes), which Google says gives high confidence of approximate correctness but does not prove exact equivalence. Google says its software tests 60 billion gates per second on one CPU core.

The three benchmarks target bottlenecks in a fusion-energy simulation, in an optimization algorithm called Decoded Quantum Interferometry, and in modeling FeMoCo, the iron-molybdenum cluster at the core of the nitrogen-fixing enzyme nitrogenase. Entries must pass an open-source verifier while lowering a score based on qubit and gate counts. The Quantum Insider reports a $150,000 pool, including $50,000 for first place, a $10,000 prize for the leaderboard at 20 November and a prize for the longest-running leader through 4 January 2027.

The companion paper, posted to arXiv on 16 October 2026 and not yet peer reviewed, cites a precedent: in an earlier public challenge on elliptic-curve cryptography circuits, more than 100 participants, most without a quantum computing background, used AI coding agents to cut Toffoli counts (the number of a costly three-qubit gate) by roughly half. Google also says its internal Gemini runs show all three benchmarks can be improved beyond circuits reported to date, and that it published a hash of those circuits to reveal after the contest.

Japan's prizes, read closely

NEDO, which operates under Japan's Ministry of Economy, Trade and Industry, presented its first-season awards on 15 October 2026. According to IBM, the challenge drew 87 applications across three tracks (Society 5.0, Quality of Life and Cool Japan), offered ¥40 million, ¥20 million and ¥10 million for first, second and third place, and awarded nine prizes, with no first prize in two tracks because of the high benchmarks required.

IBM says all nine winning teams used its quantum computers and six used them exclusively. The context matters: NEDO's October 2025 release lists several free computing environments, including Fujitsu superconducting and QuEra neutral-atom machines at AIST, IBM and Quantinuum systems at RIKEN, Quantinuum cloud access, and Toshiba and Fixstars optimization tools, and IBM says 65 of 80 participating teams, about 81 percent, chose its platform. Quantum Computing Report adds that separate sponsor awards came from a partnership backed by Quantinuum, Mitsui & Co., Mitsubishi Estate and Toshiba.

The winning work is exploratory. IBM says the Quality of Life winner, Shionogi, produced its final results by simulation, and that two teams designing bacterial combinations quantified or compared the conditions under which quantum advantage could appear rather than demonstrating it. IBM's account cites no peer-reviewed papers; it says one team's paper is in preparation.

What this says about useful quantum computers

The proof and the contest answer different questions, and neither gives a date. The Stony Brook result, if it holds up under review, sets a permanent ceiling in its model: no better hardware will let a quantum algorithm efficiently produce a welded-tree route. The lesson for a non-specialist is that quantum speedups are narrow; a large advantage on one version of a task can vanish when you ask for slightly more, here the route instead of just the destination.

The contest points the other way. It assumes the useful targets are already known and asks how cheaply they can be run, on Google's argument that every qubit and gate removed lowers the bar hardware must clear. Progress would bring specific applications closer, but the contest measures circuit counts, not years, and it accepts approximate rather than proven correctness. The NEDO results sit between the two: teams are trying applications on current machines, yet the strongest claims in IBM's account concern where an advantage might appear.

The proof and the contest share one thread: both turn on what a classical computer can keep track of. The proof says recording a route destroys the interference behind the speedup; the contest deliberately limits itself to circuit pieces that create no new superpositions so classical machines can check them. What would actually answer the timing question is not yet public: peer review and a tight bound for the maze proofs, and, after the contest closes, before-and-after resource estimates for the three benchmarks translated into error-corrected hardware requirements and set against vendors' roadmaps.