Two UC Berkeley researchers collaborating with Nokia Bell Labs have designed a chip that can efficiently solve an important class of computational problem once thought to require quantum computers. The potential for their research is enormous, helping to solve some of the most difficult computational tasks in fields as diverse as 5G communications, power grid management, smart factory optimization, and drug discovery.
On Thursday, the 2019 Nokia Bell Labs Prize was awarded to PhD Student Tianshi Wang and Jaijeet Roychowdhury of the Electrical Engineering and Computer Sciences Department at the University of California at Berkeley. Their submission, “A Classical Spin on Quantum Computing”, won over a panel of judges that included Nobel Laureate Bob Wilson, Bell Labs President and Nokia CTO Marcus Weldon, computer science pioneer Al Aho, and former Bell Labs Prize winners Samory Kpotufe and Kaushik Sengupta. Along with the prize trophy, Wang and Roychowdhury received a check for $100,000.
The duo demonstrated a compact room-temperature system, based on the synchronization of electronic oscillators, that can lead to much greater time and energy efficiency in computation. This oscillator-based system is uniquely suited to tackle a wide range of computational tasks known as “discrete optimization” problems.
A discrete-optimization problem is one that has a well-defined set of discrete solutions, the number of which can grow enormous as the number of variables or choices increases. For instance, take the problem of optimizing a car’s route through a city. At the start of the trip, the driver might be presented with choice to take street A, B or C. Then, depending on which route option selected, he or she would then be presented with a new set of street choices, and so forth. This branching leads to a potentially exponential number of possible paths. This exponential growth makes the goal of optimization – picking the best of these paths – computationally hard.
Now apply that problem to a ride-sharing service like Uber, where hundreds of drivers in a single area are assigned in real-time to hundreds of different passengers, all in different starting locations and all with different destinations. This produces multitudes of possible driver/passenger/route possibilities. Making the optimal rideshare assignments – while maximizing efficiency and profit – becomes enormously complex. Here you have a classic, though straightforward, discrete optimization problem.
That’s where Wang and Roychowdhury’s solution starts to shine. As these discrete-optimization problems become larger and more complicated, they move beyond classical computing’s ability to efficiently solve them.
“Traditionally, people believe that in order to do this kind of physical computation you need quantum effects and to build something called quantum annealers,” Wang said. “Our approach uses classical physics to do essentially the same thing. It has many advantages. A single chip can contain millions of ‘spins,’ which is far beyond today’s quantum annealers. Also, it is immediately scalable using standard CMOS technologies. You can’t put a quantum computer on a phone, but you can put our chip onto a phone.”
The possible applications for Wang and Roychowdhury’s innovation are numerous, but one potential use case particularly intrigues Nokia Bell Labs: industrial automation. The future smart factory floor is a potential minefield of discrete optimization problems. AI-powered orchestration systems must schedule instructions to thousands of individual machines and robots. Power must be optimized to each of those machines and robots for the specific tasks they’re engaged in at any given moment. Robotic vehicles must be routed across the factory floor along the most efficient paths possible. The typical robotic arm contains multiple joints and actuators, resulting in an exponentially large range of possible motions. Each of these different smart factory elements constitutes a difficult discrete optimization problem on its own, but combining them compounds those problems to mind-boggling levels. These, however, are exactly the types of problems for which Wang and Roychowdhury’s oscillator-based system is designed.
The Bell Labs Prize process also exposed the two researchers to possible applications in the field of communications. Working with their Bell Labs mentors, they realized that their oscillators could be put to use in the 5G network, solving the complex discrete-optimization tasks involved in 5G New Radio decoding and MIMO demultiplexing. Wang and Roychowdhury plan to make those 5G technologies their priority as they work on the next implementation of their chip. Nokia Bell Labs hopes to continue its collaboration with the pair, making the 5G network one of the first applications of the technology.
“The decision was tough, but Tianshi and Jaijeet’s research proposal was the most compelling,” said Weldon, who chaired the judging panel. “We congratulate them on winning this year’s prize and our research teams look forward to working together in this exciting area of technology.”
Wang and Roychowdhury weren’t the only honorees at the Bell Labs Prize. Sheng Xu, assistant professor in the Department of Nanoengineering at University of California at San Diego, took second prize and $50,000 for his submission, “There is plenty of room under the skin: A wearable’s perspective”. Meanwhile, third place and $25,000 went to the team of Maximilian Arnold, Sebastian Cammerer, Sebastian Dörner, Stephan ten Brink, all of Stuttgart University, Germany, for their submission, “Leveraging 5G Infrastructure for a Robust Positioning System”.
For further details about the Bell Labs Prize and the finalists, see our web page.