In a paper recently published in PRX Quantum, Microsoft Azure Quantum researchers Guang Hao Low and Yuan Su, with collaborators Yu Tong and Minh Tran, have developed faster algorithms for quantum simulation. One of the most promising applications of quantum computers is to simulate systems governed by the laws of quantum mechanics. Efficient quantum simulations have the potential to revolutionize many fields, including materials science and chemistry, where problems with high industrial relevance can be intractable using today’s supercomputers. Realizing this promise will require not only experimental progress, but also algorithmic advances that reduce the required quantum hardware resources. Doing so helps prepare our future scaled quantum computers to tackle challenging computational problems in the real world.
In their paper, Complexity of Implementing Trotter Steps, the authors improve upon pre-existing algorithms that rely on the so-called product formula methods, which date back to the 1990s when the first quantum simulation algorithm was proposed. The underlying idea is quite straightforward: we can simulate a general Hamiltonian system by simulating its component terms one at a time. In most situations, this only leads to an approximate quantum simulation, but the overall accuracy can be made arbitrarily high by repeating such Trotter steps sufficiently frequently.
Overcoming the complexity barrier
So, what are the resources needed to run this algorithm on a quantum computer? The algorithm repeats an elementary Trotter step multiple times, hence the total complexity is given by the number of repetitions multiplied by the cost per step, the latter of which is further determined by the number of terms in the Hamiltonian. Unfortunately, this is not very attractive for long-range quantum systems as the number of terms involved can be too big to be practical. Consider, for instance, a system with all-to-all interactions. If the size of the system is N, then the number of terms is N2, which also quantifies the asymptotic cost of Trotter steps. As a result, we are basically paying a quadratically higher cost to solve a simulation problem of just linear size. This issue becomes even worse for more general systems with many-body interactions. The question to ask then is—is there a better implementation whose cost does not scale with the total number of Hamiltonian terms, overcoming this complexity barrier?
The answer to this question, as the paper shows, is twofold. If terms in the Hamiltonian are combined with arbitrary coefficients, then this high degree of freedom must be captured by any accurate quantum simulation, implying a cost proportional to the total term number. However, when the target Hamiltonian is structured with a lower degree of freedom, the paper provides a host of recursive techniques to lower the complexity of quantum simulation. In particular, this leads to an efficient quantum algorithm to simulate the electronic structure Hamiltonian, which models various important systems in materials science and quantum chemistry.
Recursive techniques have played an essential role in speeding up classical algorithms, such as those for sorting, searching, large integer and matrix multiplication, modular exponentiation, and Fourier transformations. Specifically, given a problem of size N, we do not aim to solve it directly; instead, we divide the target problem into M subproblems, each of which can be seen as an instance of the original one with size N/M and can be solved recursively using the same approach. This implies that the overall complexity C(N) satisfies the relation: C(N) = M C(N/M) + f(N), with f(N) denoting the additional cost to combine solutions of the subproblems. Mathematical analysis yields that, under certain realistic assumptions, the overall complexity C(N) has the same scaling as the combination cost f(N) up to a logarithmic factor—a powerful result sometimes known as “the master theorem.” However, combining solutions can be much easier to handle than solving the full problem, so recursions essentially allow us to simplify the target problem almost for free!
Given the ubiquitous nature of recursions in classical computing, it is somewhat surprising that there were not many recursive quantum algorithms available. The paper from Low, Su, and collaborators develops recursive Trotter steps with a much lower implementation cost, suggesting the use of recursion as a promising new way to reduce the complexity of simulating many-body Hamiltonians.
Quantum solutions
The paper’s result applies to a variety of long-range interacted Hamiltonians, including the Coulomb interaction between charged particles and the dipole-dipole interaction between molecules, both of which are ubiquitous in materials science and quantum chemistry—a primary target application of quantum computers. In physics, impressive controls in recent experiments with trapped ions, Rydberg atoms, and ultracold atoms and polar molecules have enabled the possibility to study new phases of matter, which contributes to a growing interest in simulating such systems.
This research is part of the larger quantum computing effort at Microsoft. Microsoft has long been at the forefront of the quantum industry, serving as a pioneering force in the development of quantum algorithms tailored for simulating materials science and chemistry. This includes earlier efforts using quantum computers to elucidate reaction mechanisms in complex chemical systems targeting the open problem of biological nitrogen fixation in nitrogenase, as well as more recent quantum solutions to a carbon dioxide fixation catalyst with more than one order of magnitude savings in the computational cost.
The new results from the current work represent Microsoft’s continuing progress to develop solutions for classically intractable problems on a future quantum machine with Azure Quantum.
Learn more
- Want to learn more about Azure Quantum? We invite you to check-out our Microsoft Quantum Innovator Series.
- If you are interested in connecting, with our Azure Quantum team, please reach out at: QuantumInnovation@microsoft.com.