Quantum Computing

Developing useful quantum algorithms using intermediate-term quantum computers

The research at CQST focuses on developing quantum algorithms for problems that can be solved using both near/intermediate-term quantum devices as well as fully fault-tolerant quantum computers. We collaborate with several leading groups globally. Check out the publications on quantum computation at CQST here or here.

We are currently in the so-called Noisy Intermediate-scale Quantum (NISQ) era, which is characterized by noisy quantum circuits and a limited number of noisy qubits. Over the past few years, researchers have been actively exploring whether, using these devices, one can develop quantum algorithms of practical interest that offer a provable quantum speedup. Indeed, quantum algorithms tailored to NISQ devices have been heuristic in nature – performance guarantees have been absent. One of the research endeavors at CQST is to provide a theoretical understanding of the performance of such quantum algorithms.

Additionally, with improvements in qubit quality and overall quantum hardware, we are transitioning away from the NISQ-era. However, the devices that will become immediately after the current stage, won’t have the capabilities of a fully programmable, fault-tolerant quantum computer. These devices, known as early fault-tolerant quantum computers, are characterized by short-circuit depth and a limited number of logical qubits. At CQST, we are currently exploring whether useful quantum algorithms can be run using these devices with a provable quantum speedup. We have recently demonstrated that the generic algorithmic paradigm of Linear Combination of Unitaries can indeed be implemented using these devices. This has led to the development of novel quantum algorithms for ground state preparation and solving quantum linear systems. Both these algorithms find widespread applications in areas ranging from quantum chemistry, condensed matter physics to optimization and machine learning. We are also exploring whether one can leverage other models of quantum computation in the intermediate term for solving practical problems.

Quantum algorithms for fully-fault tolerant quantum computers

At CQST, we develop novel quantum algorithms for various problems. This includes enhancing the understanding of state-of-the-art quantum algorithmic techniques such as quantum singular value transformation and frameworks such as block encoding. We have recently developed the first quantum algorithms for regularized least squares – a widely used technique in machine learning and statistics. Indeed, there is special emphasis on developing quantum linear algebra-based algorithms as they find broad applicability. We are also working on designing better quantum algorithms for sampling and optimization – two areas where quantum computers have the potential to offer significant quantum speedups.

We also work on other quantum computational models such as quantum walks and adiabatic quantum computing. For the former, we have recently shown that the problem of finding marked vertices on any graph, known as spatial search, can be solved quadratically faster using continuous-time quantum walks, closing a problem that was open for close to two decades. Additionally, we have improved the running times of fundamental quantum walk-based algorithms such as the Welded trees problem.