Source-linked AI summary
Variational Quantum algorithm for Poisson equation
Hailing Liu, Yusen Wu, Linchun Wan, Shijie Pan, Sujuan Qin, Fei Gao, Qiaoyan Wen
TL;DR
Existing Poisson-equation quantum algorithms generally require fault-tolerant computers, and Pauli-basis decompositions can grow polynomially with matrix dimension. The VQA decomposes its coefficient matrix into 2 log n + 1 simple-operator terms, minimizes a variational cost, and evaluates it with parallel Bell measurements. The simulated circuit fidelity increases with circuit depth and reaches 0.99.
Problem
Existing Poisson-equation quantum algorithms generally require fault-tolerant computers, and Pauli-basis decompositions can grow polynomially with matrix dimension.
Source: §I · pp. 1–2Method
The VQA decomposes its coefficient matrix into 2 log n + 1 simple-operator terms, minimizes a variational cost, and evaluates it with parallel Bell measurements.
Source: §I · p. 2, §III · p. 2, B. Evaluate E(θ) · p. 5Results
The simulated circuit fidelity increases with circuit depth and reaches 0.99.
Source: C. Numberical experiments · p. 5Takeaways & Limitations
The 2 log n + 1 term decomposition reduces the number of measurements, and parallel Bell measurements evaluate the cost function on a quantum computer.
Source: §IV · p. 5
Abstract
from arXiv · showhide
The Poisson equation has wide applications in many areas of science and engineering. Although there are some quantum algorithms that can efficiently solve the Poisson equation, they generally require a fault-tolerant quantum computer which is beyond the current technology. In this paper, we propose a Variational Quantum Algorithm (VQA) to solve the Poisson equation, which can be executed on Noise Intermediate-Scale Quantum (NISQ) devices. In detail, we first adopt the finite difference method to transform the Poisson equation into a linear system. Then, according to the special structure of the linear system, we find an explicit tensor product decomposition, with only $2\log n+1$ items, of its coefficient matrix under a specific set of simple operators, where $n$ is the dimension of the coefficient matrix. This implies that the proposed VQA only needs $O(\log n)$ measurements, which dramatically reduce quantum resources. Additionally, we perform quantum Bell measurements to efficiently evaluate the expectation values of simple operators. Numerical experiments demonstrate that our algorithm can effectively solve the Poisson equation.
I. INTRODUCTION
Quantum methods for the Poisson equation can be efficient, but existing approaches generally rely on fault-tolerant hardware, while NISQ devices have shallow-circuit, qubit, and fidelity constraints. The paper proposes a VQA using a compact matrix decomposition and efficient expectation-value measurements to address this setting.
I. INTRODUCTION
- Existing quantum algorithms can speed up Poisson-equation solving, but they generally require fault-tolerant quantum computers beyond current technology.The paper motivates solving the discretized linear systems because their dimensions can be very large and classical solution can be time consuming.Source: §I · p. 1
- The key design challenge is decomposing the discrete Poisson coefficient matrix into few tensor-product terms whose expectation values can be efficiently measured.Existing linear-system VQAs require both a compact decomposition and efficient evaluation of each term.Source: §I · p. 1
- The proposed decomposition uses 2 log n + 1 terms under {I, σ+, σ−}, reducing the measurement burden for the VQA.The paper also constructs observables for efficiently evaluating the cost function.Source: §I · p. 2
- The authors simulate the algorithm in ProjectQ and report that it effectively solves the Poisson equation.The paper describes the algorithm as a hybrid quantum-classical approach suited to NISQ devices.Source: §I · p. 2
II. DISCRETIZE THE POISSON EQUATION
The paper discretizes the Poisson equation with finite differences to obtain a linear system, whose solution approximates the equation’s solution. The text specifies how the one-dimensional discretization parameter and right-hand-side vector are formed.
II. DISCRETIZE THE POISSON EQUATION
- Finite differences convert the Poisson equation into a linear system, and solving that system gives an approximate solution of the equation.The described equation has Dirichlet boundary conditions on the domain D.Source: §II · p. 2
- The one-dimensional discretization divides (0, 1) into n+1 equal parts, and b is formed by sampling f(x) at the interior grid points.Source: §II · p. 2
- The paper also introduces the coefficient matrix generated by discretizing the d-dimensional Poisson equation.The supplied passage does not specify the matrix entries.Source: §II · p. 2
III. A VQA FOR POISSON EQUATION
The VQA recasts solving the discretized Poisson system as finding a Hamiltonian ground state, then minimizes a cost over parameterized quantum states. At the optimum, the generated state approximates the normalized solution state.
III. A VQA FOR POISSON EQUATION
- The algorithm maps the linear-system problem to finding the ground state of a Hamiltonian constructed from A and |b⟩.The state |b⟩ is proportional to b and can be prepared with a unitary; the ground state is the normalized A^-1|b⟩ state with eigenvalue zero.Source: §III · p. 2
- The cost E(θ) is minimized over parameterized states |ψ(θ)⟩, and the optimized circuit produces a state approximating |x⟩.The quantum computer evaluates the cost while a classical computer adjusts the gate-sequence parameters.Source: §III · p. 2
- Cost evaluation requires expectation values involving A² and A, including ⟨ψ(θ)|A²|ψ(θ)⟩ and |⟨b|A|ψ(θ)⟩|².The algorithm uses decompositions of A and A² to make these evaluations on a quantum computer.Source: §III · p. 2
- The method section focuses on the one-dimensional discretized matrix and assumes n = 2^m for positive integer m.Source: §III · p. 2
- The algorithm’s workflow decomposes A and A², evaluates the cost on a quantum computer, and updates θ classically until the change in cost is within ε.The figure describes outputting the optimized state after the update condition is met.Source: Figure 1 · p. 3
A. An explicit decomposition of A and A2
The section uses the block structure of the discretized Poisson matrices and a recursive algorithm to obtain explicit tensor-product decompositions. The resulting term counts grow linearly with the number of qubits, including for the d-dimensional case.
A. An explicit decomposition of A and A2
- Using the special structures of A and A2, the authors first write A and A2 as block matrices, then apply the recursive algorithm to find their explicit decompositions.Source: A. An explicit decomposition of A and A2 · p. 3
- A_m has 2m + 1 tensor-product terms, reducing the decomposition to a number linear in the logarithm of the matrix dimension.The terms use the simple operators {I, σ+, σ−}.Source: A. An explicit decomposition of A and A2 · p. 3
- A_2m has 4m + 1 terms, while the decomposition for the d-dimensional Poisson matrix has d(2m + 1) terms.The method is also applied to general tridiagonal and pentadiagonal Toeplitz matrices used for partial differential equations [24–27].Source: A. An explicit decomposition of A and A2 · p. 4
B. Evaluate E(θ)
The cost function is evaluated from expectation values of terms in the decomposed operators. Bell measurements handle the stated observables, while computational-basis measurements evaluate C.
B. Evaluate E(θ)
- The cost evaluation directly measures the expectation value of each term in X ⊗ A and A^2 = B − C.Source: B. Evaluate E(θ) · p. 5
- Bell measurements provide expectation values for X ⊗ A and B, and can be performed in parallel for all qubit pairs using Hadamard and CNOT gates [39].The protocol attaches an ancilla qubit to the state being measured.Source: B. Evaluate E(θ) · p. 5
- Computational-basis local measurements evaluate C because σ−σ+ and σ+σ− are Hermitian projectors.Linearity then allows the cost function E(θ) to be evaluated on a quantum computer.Source: B. Evaluate E(θ) · p. 5
C. Numberical experiments
The numerical experiments simulate the algorithm for one-dimensional Poisson systems using a QAOA variational circuit. Fidelity with the solution state increases with circuit depth and reaches 0.99.
C. Numberical experiments
- The simulations use 2–6 qubits for the one-dimensional Poisson equation, with b sampled from f(x) = x at interior grid points.They use ProjectQ and a QAOA ansatz; the variational parameters are randomly initialized and optimized with BFGS.Source: C. Numberical experiments · p. 5
- The circuit example uses m = 3 qubits, with RX and RZ rotations arranged in repeated blocks.The caption specifies eight layers and seven parameters per layer.Source: Figure 3 · p. 5
- Fidelity |⟨x|ψ(θopt)⟩| increases as circuit layers p increase and can reach 0.99.The insert in Fig. 4 plots the minimum number of layers required to guarantee fidelity 0.99.Source: C. Numberical experiments · p. 5
IV. CONCLUSION
The paper designs a VQA for the Poisson equation using a coefficient-matrix decomposition with 2 log n + 1 terms and parallel quantum Bell measurements. It also extends the decomposition approach to structured Toeplitz systems and proposes a broader decomposition idea for VQAs.
IV. CONCLUSION
- The Poisson-equation VQA decomposes its coefficient matrix into 2 log n + 1 terms, reducing measurement needs, and uses parallel quantum Bell measurements to evaluate the cost function.Here n is the coefficient matrix dimension.Source: §IV · p. 5
- As circuit layers increase, the simulated fidelity reaches 0.99; the inset reports the minimum layer count required at that threshold.The figure plots fidelity against layer and qubit counts.Source: Figure 4 · p. 6
- The decomposition method also applies to general tridiagonal and pentadiagonal Toeplitz matrices, with item counts growing linearly with the logarithm of matrix dimension.These matrices are often used to solve partial differential equations [24–27].Source: §IV · p. 6
- For VQAs involving data matrices, the paper proposes decomposing them with efficiently measurable simple operators that need not be Pauli or Hermitian operators.The authors suggest this approach may stimulate VQAs for practical applications.Source: §IV · p. 6
Appendix A: Decomposition of the general tridiagonal and pentadiagonal Toeplitz matrices
The appendix applies the decomposition method to general tridiagonal and pentadiagonal Toeplitz matrices. A recursive algorithm decomposes the matrices under simple operators, with the reported term counts depending on m.
Appendix A: Decomposition of the general tridiagonal and pentadiagonal Toeplitz matrices
- The appendix considers general tridiagonal and pentadiagonal Toeplitz matrices, assuming n = 2m for positive integer m.The matrices are noted as common in solving partial differential equations [24–27].Source: Appendix A · p. 6
- A recursive algorithm finds explicit tensor-product decompositions of W and V under the simple operators {I, σ+, σ−}.The displayed expressions give the respective decompositions.Source: Appendix A · p. 7
- W has 2m + 1 decomposed terms, while V has 4m − 1.Source: Appendix A · p. 7