There can be few scientists who can legitimately call themselves a “quantum mechanic”. Still, Seth Lloyd is a Professor of mechanical engineering, but works on the fundamentals of quantum technology and science and has contributed to a famous quantum algorithm named HHL and QAOA for optimization, which companies such as D-wave have commercially exploited. Here we delve into Seth Lloyd’s background, his seminal quantum work and some of his writings which have inspired a generation of scientists to think of the universe as one giant quantum computer.
The ‘Quantum Mechanic’
Professor of Mechanical Engineering and physics at Massachusetts Institute of Technology (MIT). Seth Lloyd received his bachelor’s degree in physics from Harvard in 1982 and PhD from Rockefeller in 1998. His academic interests are the following: Quantum information: quantum computation and quantum communications, Quantum control and measurement: quantum limits to control and sensing and Complex systems which are characterizing and managing complex systems. Seth is also an adjunct Professor at Santa Fe Institute.
He has received numerous awards and honours for his work. He has published over 200 articles and two patents, one for QRAM (storing information in quantum memory). Lloyd’s accolades include the following: 2007 Fellow of the American Physical Society and the 2012 Quantum communication, measurement, and computation prize.
We loved Seth Lloyd’s take on how the Universe is simply one big computer in his title “Programming the Universe“. Definitely worth a read and is aimed at a general audience.
QAOA – Optimization that created an entire industry
The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm developed by Seth Lloyd and others for finding approximate solutions to optimization problems. Optimization problems involve finding a good answer from a set of possible solutions, given constraints. For example, finding the shortest route between two cities is a typical optimization problem, often known as the TSP or the Travelling Salesman Problem.
Companies like D-wave have exploited the optimization methodology to create quantum annealers (see our guide to the difference between that gate-based devices) that can help various companies with optimization problem sets. Optimization has become one of the early use cases for quantum computers.
The HHL algorithm
The algorithm HHL (short for Harrow, Hassidim, and Lloyd) algorithm is a quantum algorithm designed to solve systems of linear equations and sports Lloyd in the name. It was developed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd back in 2009 and is considered to be an essential breakthrough in the field of quantum computing.
Loosely, the HHL algorithm works by using a quantum computer to efficiently find the solution to a system of linear equations of the form Ax = b, where A is a matrix and b is a vector. In classical computing (like the one you are reading this on), solving such systems of equations can be computationally expensive, especially for large matrices. However, the HHL algorithm allows a quantum computer to solve these systems much faster, in a logarithmic time in the matrix size.
The HHL algorithm has many potential applications, including Machine Learning (ML) or AI, data analysis, and optimization problems. However, it is still an area of active research, and it is not yet clear how practical it will be to implement the HHL algorithm on a real quantum computer.
The HHL algorithm uses a quantum computer to find the solution to a system of linear equations of the form Ax = b, where A is a matrix and b is a vector. It does this by first encoding the matrix A and vector b into quantum states, and then using quantum operations to manipulate these states to find the solution x.
Behind the HHL algorithm with which Seth Lloyd is commonly known is the idea to use a quantum version of the classical technique known as “Amplitude Amplification“, a technique used in other quantum algorithms such as Grover’s algorithm. The algorithm begins by preparing a quantum state that encodes the matrix A and the vector b. Then it applies a series of quantum operations to this state to amplify the amplitude (or probability) of the correct solution.
Once the correct solution has been amplified, it can be measured and extracted from the quantum state. Here is a more detailed explanation of how the HHL algorithm works:
- Encoding: The first step is encoding matrix A and the vector b into quantum states. This is done by creating a quantum register with several qubits (quantum bits) equal to the number of entries in the vector b, and then using quantum operations to initialize the qubits to the values of the vector b. The matrix A is then encoded into a quantum state using a technique called “quantum singular value decomposition” (QSVD).
- Amplification: The next step is to use the quantum version of Amplitude Amplification to amplify the correct solution’s amplitude (or probability). This is done by applying a series of quantum operations to the quantum state, which effectively “amplifies” the probability of the correct solution.
- Measurement: Once the correct solution has been amplified, it can be measured and extracted from the quantum state. This is done by using a quantum operation called “quantum inverse iteration” to “uncompute” the solution from the quantum state, and then measuring the qubits to obtain the values of the solution vector x.
The HHL algorithm allows a quantum computer to find the solution to a system of linear equations much faster than the classical computers we currently use. in a time that is logarithmic in the size of the matrix A. However, the algorithm has some limitations, such as the requirement that the matrix A be “well-conditioned,” and it is still an active research area.
QRAM: Storage in the Quantum Era
Many interesting Quantum Algorithms rely on the idea of a quantum RAM (QRAM) where qubits can be written and retrieved quickly. No practical QRAM device has been built so far. Conventional or classical computers rely on RAM (Random Access Memory) to operate. The same principle of storage needs to happen in the quantum space. Looking at the quantum zoo of equations, many algorithms will require some form of quantum storage. However, unlike classical computers, there is no defined memory or storage element for quantum computers. Lloyd has been instrumental in imagining how QRAM will work. Here are some papers from Lloyd et al.
- “Quantum random access memory” by Seth Lloyd, published in Physical Review Letters in 1996. This paper introduced the concept of QRAM and demonstrated its feasibility through theoretical and experimental studies.
- “Architectures for a quantum random access memory” by Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccon. The paper analyzed two different RAM architectures (the conventional fanout and the “bucket brigade”) and proposed some proof-of-principle implementations.
He has produced several papers on quantum memory. He has proposed several schemes for implementing QRAM, including nuclear magnetic resonance (NMR) techniques, trapped ions, and superconducting circuits. Of course, there is wider work done in developing algorithms and protocols for accessing and manipulating quantum memory, including methods for error correction and fault tolerance.
Anyone who has heard Prof. Seth Lloyd speak will testify to his amazing ability to convey complex ideas in a way that makes sense, a true communicator and orrator. He has an aversion to powerpoint so expect some great verbal explanations and takeaways as he takes on the mantle of making it his job to explain some of worlds most challenging topics.
