Quantum algorithms for Linear Algebra

Linear algebra lies at the heart of many quantum algorithms, powering applications from solving linear systems to machine learning. Many tasks can be phrased as applying a function of an operator to a quantum state, but the challenge is that these operators are not generally unitary, while quantum computers naturally implement only unitary transformations. To overcome this, we introduced block encoding, which embeds an operator into a larger unitary and unifies several models of quantum input [1]. Using this framework, techniques like the Linear Combination of Unitaries (LCU) and Quantum Singular Value Transformation (QSVT) enable a wide range of transformations on quantum states. Building on these tools, we have developed state-of-the-art algorithms for simulating quantum dynamics, solving linear systems, performing regression, and preparing ground states of Hamiltonians — demonstrating how quantum computers can tackle some of the most important linear algebra tasks efficiently [2, 3].

Resource-efficient quantum algorithms

Many powerful quantum algorithms are difficult to implement on today’s hardware because they require deep circuits, numerous ancilla qubits, or complex multi-qubit controls. Our research focuses on resource-efficient approaches that maintain provable quantum advantages while reducing these costs. For example, we have introduced new methods for Linear Combination of Unitaries (LCU) that reduce or even eliminate the need for ancilla qubits, enabling implementations suitable for near-term devices [3]. Similarly, our work on Quantum Singular Value Transformation (QSVT) removes the dependence on block encodings (which can be extremely expensive to construct), thereby lowering both ancilla and circuit overhead while achieving near-optimal complexity [4]. In addition, we have developed a randomized QSVT scheme, which further improves practicality for near-term quantum devices by simplifying implementation and reducing resource requirements [5]. These techniques have been applied across a wide range of quantum tasks, including Hamiltonian simulation, ground state preparation, solving quantum linear systems, quantum walks, and simulating open quantum systems [6]. Together, they demonstrate that advanced quantum algorithms can be executed efficiently on both intermediate-term and fully fault-tolerant quantum computers, bridging the gap between theoretical promise and experimental feasibility.

Quantum Walks

Quantum walks are the quantum analogue of classical random walks and serve as a versatile framework for developing new quantum algorithms. They are also a universal model for quantum computation. Our research advances both the theory and applications of quantum walks. A central problem is spatial search, which involves finding marked vertices in a graph. Building on earlier work by Childs and Goldstone (2004) and Szegedy (2004), we have developed a continuous-time quantum walk algorithm that achieves a generic quadratic speedup for any graph and any number of marked elements [7, 8, 9]. Beyond spatial search, we study fundamental properties of quantum walks, including hitting and mixing times on random graphs [7, 10], and have improved the performance of the quantum-welded trees problem, one of the few algorithms offering an exponential advantage, by a polynomial factor [11]. These contributions deepen our understanding of quantum walks and highlight their power as a computational tool for both theory and practical algorithm design.

Adiabatic Quantum Optimisation

Adiabatic Quantum Optimisation (AQO) is a quantum approach to solving optimization problems by slowly evolving a system from a simple, easily prepared initial state to a final state that encodes the solution. Our research shows that AQO can provide a quadratic speedup over classical brute-force search for a broad class of optimization problems, resolving a long-standing open problem where a lower bound was known but an explicit algorithm achieving it was absent. At the same time, we have identified important limitations: the algorithm’s success depends on precisely tracking the energy gap during the evolution, and predicting the position of the avoided crossing (where the two lowest energy levels are closest) is crucial for obtaining a quantum advantage. We prove that approximating this position is NP-hard, and computing it exactly is #P-hard. By highlighting both the strengths and constraints of AQO, our work clarifies when quantum computers can achieve genuine advantages for optimization tasks and guides the development of more efficient and practical adiabatic algorithms [12].