Brief Summary
This session focuses on block encoding, a fundamental concept in quantum algorithms, with applications in quantum chemistry and differential equations. The presentation is divided into two parts: the first explains famous quantum algorithms for block encoding, such as LCU and prepare-select-prepare, and the second discusses block encoding for differential equations. Key points include:
- Block encoding is essential for encoding computational problems into quantum circuits.
- It involves embedding a non-unitary matrix (like a Hamiltonian) into a larger unitary matrix.
- The prepare-select-prepare algorithm is a key technique for block encoding, especially when dealing with Hamiltonians expressed as a linear combination of Pauli words.
- Different methods are required for different inputs, highlighting the need for ongoing research in this area.
Introduction
The session is part of a summer workshop, focusing on block encoding, a key concept in quantum algorithms. Block encoding serves as a data access model for a given matrix. GMO Alensor Lin from Xanadu, an expert in quantum machine learning and algorithms, will lead the session. He has experience in both research and education in quantum computing.
Why Block Encoding?
GMO discusses his experience with block encoding in various projects at Xanadu, including the quantum algorithm toolkit and a collaboration with Rolls-Royce. He emphasizes the importance of block encoding as a fundamental technique in quantum algorithms, often overlooked in introductory quantum computing courses. The presentation is divided into two parts: quantum algorithms for block encoding and block encoding for differential equations.
Basic Definitions: Quantum Computing and Hamiltonians
Quantum computing involves encoding computational problems into quantum circuits, evolving quantum states via unitary operators, and recovering classical information through measurements. Encoding is a key aspect, exemplified by quantum chemistry, where molecules are defined through Hamiltonians. A Hamiltonian is a Hermitian matrix with physical meaning. Quantum circuits can be represented as matrices, but Hamiltonians cannot be directly used as quantum gates because quantum gates must be unitary, preserving norms and reversibility.
Encoding the Hamiltonian: Unitary Transformations
Since a Hamiltonian (H) is not unitary, directly using it as a quantum gate is not possible. However, e^(iH) is unitary. This property is proven using the fact that the inverse of e^(iH) is e^(-iH), and the dagger of e^(iH) is also e^(-iH). Therefore, the Hamiltonian can be encoded through this exponential form using techniques called product formulas, such as Trotter-Suzuki decomposition, to approximate the gate by multiplying simpler gates.
Block Encoding: Embedding the Hamiltonian
Block encoding is an alternative technique to encode information by embedding the Hamiltonian as a block in the top left of a larger matrix. The goal is to find values for the other parts of the matrix such that the entire matrix becomes unitary. This is always possible. The main examples of block encoding occur when the Hamiltonian is expressed as a linear combination of Pauli words (e.g., X, Y, Z, Identity). These Hamiltonians are common in quantum chemistry, and the number of Pauli words is typically sparse compared to the size of the space.
Algorithm for Block Encoding: Linear Combination of Pauli Words
The main algorithm for block encoding focuses on scenarios where the matrix is expressed as a linear combination of Pauli words. Each Pauli term has a unitary representation. The challenge is to combine these terms with additions and weights. This can be achieved by building a quantum state that encodes the coefficients. For example, with coefficients 1/4, 1/3, and 1/4, a state with three basis states is created, codifying the coefficients.
Combining Coefficients and Pauli Words
To associate each coefficient with its corresponding Pauli word, an index operator approach is used. For each index, a tensor product is performed with the appropriate Pauli operator. This is implemented using circuits where a preparation box generates the state with the coefficients, and controlled operations apply the correct Pauli operator based on the state of the index qubits.
Creating a Block Encoding of the Hamiltonian
To check the top-left element, project with zeros. This reveals only the first coefficient of the Hamiltonian. To move all the information to the first position, multiply the vector by a matrix with ones in the first row. This operation is achieved using Hadamard gates, which create equal superpositions. However, this introduces a factor that decreases exponentially with the number of qubits, which is not ideal.
Improving the Algorithm: Square Roots and Coefficient Multiplication
To eliminate the exponential decay factor, load the square root of the coefficients instead of the coefficients themselves. Apply the same circuit, resulting in a vector with square roots of the coefficients and Pauli words. Then, multiply by a matrix with the square roots of the coefficients in the first row. This ensures that when multiplied, the square roots combine to give the original coefficients, creating the desired Hamiltonian without the exponential decay.
Block Encoding for Differential Equations: Diagonal Matrices
Not all matrices can be efficiently represented as a sum of Pauli operators. Differential equations often involve diagonal matrices. To solve a differential equation on a quantum computer, discretize the variables and approximate derivatives. This leads to a system of equations that can be organized into a matrix, often a three-diagonal matrix. Solving the differential equation is then equivalent to solving this system using quantum algorithms like HHL or matrix inversion via quantum signal processing.
Encoding One-Diagonal Blocks
To create a one-diagonal block encoding, multi-controlled rotation-Y gates are used. These gates have a matrix form where the cosine of the rotation angle appears in the controlled position. By concatenating and multiplying these controlled rotations, a diagonal block encoding can be created. This is often referred to as a multiplexer or uniform control rotation.
Quantum Arithmetic for Diagonal Positioning
Quantum arithmetic is used to position the diagonal in different locations. Applying a quantum adder with +1 moves the diagonal one position to the right, while -1 moves it to the left. This allows for the creation of a diagonal block encoding in any desired position.
Generalizing to Tridiagonal Matrices
To encode tridiagonal matrices, combine the techniques for one-diagonal blocks with the prepare-select-prepare algorithm. Each diagonal is encoded independently using multiplexers and quantum arithmetic. The prepare-select-prepare algorithm then combines these individual terms. The initial state is an equal superposition of the number of diagonals. The select block applies the appropriate unitary operation based on the index, and the adjoint of the preparation step adds the diagonals together.
Conclusions
Block encoding is a fundamental block in many quantum subroutines, appearing naturally in quantum chemistry and differential equations. Different inputs require different methods, and this remains an active area of research.
