Tag Archives: Quanta

Machine Learning Gets a Quantum Speedup


Two teams have shown how quantum approaches can solve problems faster than classical computers, bringing physics and computer science closer together.

For Valeria Saggio to boot up the computer in her former Vienna lab, she needed a special crystal, only as big as her fingernail. Saggio would place it gently into a small copper box, a tiny electric oven, which would heat the crystal to 77 degrees Fahrenheit. Then she would switch on a laser to bombard the crystal with a beam of photons.

This crystal, at this precise temperature, would split some of those photons into two photons. One of these would go straight to a light detector, its journey finished; the other would travel into a tiny silicon chip — a quantum computing processor. Miniature instruments on the chip could drive the photon down different paths, but ultimately there were only two outcomes: the right way, and the many wrong ways. Based on the result, her processor could choose another path and try again.

The sequence feels more Rube Goldberg than Windows, but the goal was to have a quantum computer teach itself a task: Find the right way out.

Read the full story in Quanta Magazine

Surprising Limits Discovered in Quest for Optimal Solutions

Quanta Magazine

Algorithms that zero in on solutions to optimization problems are the beating heart of machine reasoning. New results reveal surprising limits.

Our lives are a succession of optimization problems. They occur when we search for the fastest route home from work or attempt to balance cost and quality on a trip to the store, or even when we decide how to spend limited free time before bed.

These scenarios and many others can be represented as a mathematical optimization problem. Making the best decisions is a matter of finding their optimal solutions. And for a world steeped in optimization, two recent results provide both good and bad news.

In a paper posted in August 2020, Amir Ali Ahmadi of Princeton University and his former student, Jeffrey Zhang, who is now at Carnegie Mellon University, established that for some quadratic optimization problems — in which pairs of variables can interact — it’s computationally infeasible to find even locally optimal solutions in a time-efficient manner.

But then, two days later, Zhang and Ahmadi released a second paper with a positive takeaway. They proved that it’s always possible to quickly identify whether a cubic polynomial — which can feature three-way interactions between variables — has a local minimum, and to find it if it does.

The limits are not what their discoverers expected.

Read the full story in Quanta Magazine

The Coach Who Led the U.S. Math Team Back to the Top


Po-Shen Loh has harnessed his competitive impulses and iconoclastic tendencies to reinvigorate the U.S. Math Olympiad program.

Po-Shen Loh has resurrected the United States International Mathematical Olympiad team, leading it to four first-place rankings in the last six years as the team’s head coach.

But in 2002, when a friend suggested Loh apply for an open position as a grader with the team, he hesitated. “I had never thought to apply before,” Loh said. “Not because I didn’t want to. But because I thought there are better people out there.”

He eventually agreed, and by the end of the team’s June 2002 training program, he’d made an impression. “Somehow I got voted best lecturer,” he said. In 2013 the Mathematical Association of America, which coordinates the team, asked Loh to become the head coach. He accepted, and two years later the U.S. achieved a top ranking in the IMO for the first time in 21 years.

Read the full story in Quanta Magazine

New Quantum Algorithms Finally Crack Nonlinear Equations


Two teams found different ways for quantum computers to process nonlinear systems by first disguising them as linear ones.

Sometimes, it’s easy for a computer to predict the future. Simple phenomena, such as how sap flows down a tree trunk, are straightforward and can be captured in a few lines of code using what mathematicians call linear differential equations. But in nonlinear systems, interactions can affect themselves: When air streams past a jet’s wings, the air flow alters molecular interactions, which alter the air flow, and so on. This feedback loop breeds chaos, where small changes in initial conditions lead to wildly different behavior later, making predictions nearly impossible — no matter how powerful the computer.

“This is part of why it’s difficult to predict the weather or understand complicated fluid flow,” said Andrew Childs, a quantum information researcher at the University of Maryland. “There are hard computational problems that you could solve, if you could [figure out] these nonlinear dynamics.”

That may soon be possible. In separate studies posted in November, two teams — one led by Childs, the other based at the Massachusetts Institute of Technology — described powerful tools that would allow quantum computers to better model nonlinear dynamics.

Read the full story in Quanta Magazine