Quantum-Inspired Algorithm Approaches Theoretical Limit in Compressed Sensing

NTT Research, Inc., a division of NTT (TYO:9432), today announced that scientists from Tokyo Institute of Technology (Tokyo Tech) and NTT Research have successfully developed compressed sensing as the first application of the cyber coherent Ising machine (cyber-CIM), a quantum-inspired algorithm that can be implemented on a modern digital platform today or hybrid quantum-classical machine in the future. They shared their findings in a paper, titled “L0 regularization-based compressed sensing with quantum-classical hybrid approach,” published in May 2022, in the journal Quantum Science and Technology. Compressed sensing is a signal processing technique used in medical imaging, astronomy and elsewhere that requires extremely high levels of processing on existing computers to discard massive amounts of data with no useful information. In an exercise optimizing L0-regularization-based compressed sensing (L0-RBCS), the cyber-CIM approached the theoretical limit of compressed sensing and outperformed the commonly used default method. L0-RBCS is a non-deterministic polynomial-time (NP)-hard combinatorial problem that uses sparse regularization with L0-norm for regression analysis under the constraint of maximum zero elements for a source signal. Sparse regularization with L1-norm performs both variable selection and regularization, a technique to reduce errors and prevent overfitting. The commonly employed L1-RBCS method including the least absolute shrinkage and selector operator (LASSO) uses a computationally easier but less accurate form of sparse regularization, which approaches compressed sensing through approximation.

This joint research between Tokyo Tech and NTT Research grew out of an agreement signed in 2020 that called for collaboration between the NTT Research Physics & Informatics (PHI) Lab and the laboratory of Dr. Toru Aonishi in the Tokyo Tech School of Computing. Co-authoring the paper with Dr. Aonishi are Dr. Kazushi Mimura of Hiroshima City University, Dr. Masato Okada of The University of Tokyo and PHI Lab Director Yoshihisa Yamamoto. NTT Research is funding a five-year cyber-CIM project with Tokyo Tech, which also includes work on drug discovery. Both compressed sensing and drug discovery are NP-hard combinatorial optimization problems, which a CIM is purpose-built to solve. The CIM, in its cyber and physical constructions, is a dense network of optical parametric oscillators (OPOs) programmed to solve problems that are mapped to an Ising model, which is a mathematical abstraction of magnetic systems composed of competitively interacting spins, or angular momentums of fundamental particles. Previous work has focused mainly on how quantum oscillator networks solve combinatorial optimization problems. This is the first known practical application of the cyber-CIM.

“Our progress in this application-oriented work has been very exciting,” Dr. Yamamoto said. “We show in this paper how the hybrid system performance in principle approaches the theoretical limit of compressed sensing, exceeds that of the default LASSO method and in practical situations exceeds its estimation accuracy.”

The quantum-classical hybrid system proposed by the authors performs CIM and classical digital processing (CDP) in alternating steps. To evaluate the performance of the cyber-CIM algorithm in solving L0-RBCS, they introduced a truncated Wigner stochastic differential equation (W-SDE) as a model for a system of “n” number of OPOs. The W-SDE falls within the non-theoretical, phase-space method of quantum mechanics, which was invented to circumvent the impossibility (due to limited resources of modern digital computers) of direct numerical simulation in an open quantum system with dissipation. Macroscopic equations were derived by applying statistical mechanics to the W-SDE. What was demonstrated in the paper is the application of L0-RBCS on the cyber-CIM, which can be deployed now on a modern digital platform. The concept, however, can be extended to a hybrid quantum-classical machine in the future. The paper expects improved performance, including reduced energy costs, in that scenario, but that prediction will need to be tested on a physical machine. For now, the team continues to focus on the interaction between CIM and applications.

“Performance of L0 regularization-based compressed sensing has been improved further by employing a new CIM algorithm, called CIM-CAC [Chaotic Amplitude Control],” said Dr. Aonishi. “We are preparing a new manuscript on this.”

According to another paper, “Coherent Ising Machines with Optical Error Correction Circuits,” co-authored by Dr. Yamamoto and published in Advanced Quantum Technologies in September 2021, CIM-CAC can refer to either a system of differential equations integrated as a digital algorithm or an optical CIM that emulates the corresponding equations.

In addition to its work with Tokyo Tech, the NTT Research PHI Lab has established joint research agreements in pursuit of the ambitious goal of radically redesigning computers, both classical and modern, with the following eight universities: California Institute of Technology (CalTech), Cornell University, Massachusetts Institute of Technology (MIT), Notre Dame University, Stanford University, Swinburne University of Technology, the University of Michigan and the University of Tokyo. It is also conducting joint research with the NASA Ames Research Center in Silicon Valley and 1QBit, a private quantum computing software company.

About NTT Research

NTT Research opened its offices in July 2019 as a new Silicon Valley startup to conduct basic research and advance technologies that promote positive change for humankind. Currently, three labs are housed at NTT Research facilities in Sunnyvale: the Physics and Informatics (PHI) Lab, the Cryptography and Information Security (CIS) Lab, and the Medical and Health Informatics (MEI) Lab. The organization aims to upgrade reality in three areas: 1) quantum information, neuroscience and photonics; 2) cryptographic and information security; and 3) medical and health informatics. NTT Research is part of NTT, a global technology and business solutions provider with an annual R&D budget of $3.6 billion.

NTT and the NTT logo are registered trademarks or trademarks of NIPPON TELEGRAPH AND TELEPHONE CORPORATION and/or its affiliates. All other referenced product names are trademarks of their respective owners. © 2022 NIPPON TELEGRAPH AND TELEPHONE CORPORATION

View source version on businesswire.com: https://www.businesswire.com/news/home/20221220005134/en/

New from @NttResearch & @tokyotech_en: the first application of the Coherent Ising Machine (CIM) to compressed sensing, implementable on digital platforms today and quantum machines of the future. #UpgradeReality #TechForGood