Solving a Linear System of Equations on a Quantum Computer by Measurement

This paper introduces a variational measurement-based algorithm for fault-tolerant quantum computers that solves linear systems by iteratively optimizing target fidelity through phase estimation, thereby overcoming limitations of previous methods regarding Pauli decomposition, condition number dependence, and measurement scaling.

The Gist

Imagine you are trying to solve a massive, complex puzzle. In the world of math, this puzzle is a system of linear equations. Think of it like a giant recipe where you have a list of ingredients (the numbers in a matrix) and a final dish you want to create (the answer). Usually, finding that perfect recipe takes a long time, especially if the list of ingredients is huge and messy (what mathematicians call a "dense" matrix).

This paper introduces a new way for quantum computers to solve these puzzles. Instead of using the standard, slow methods, the authors propose a technique they call the "Measurement Test Algorithm."

Here is how it works, explained through simple analogies:

1. The Goal: Finding the "Golden State"

In a quantum computer, information is stored in qubits, which can be in many states at once. The goal here is to find a specific state (a specific arrangement of the qubits) that represents the correct answer to the math problem.

Think of the quantum computer as a radio tuner. You want to tune it to a specific frequency (the correct answer). Right now, the radio is static-filled and playing noise. The algorithm's job is to twist the knobs until the static clears and you hear the perfect, clear signal.

2. The Old Way vs. The New Way

The Old Way (Variational Quantum Algorithms):
Previous methods were like trying to tune that radio by checking every single station one by one. To do this, the computer had to break the problem down into tiny, simple pieces (called "Pauli strings"). If the problem was complex (a "dense" matrix), there were too many pieces to check. It was like trying to count every grain of sand on a beach to find one specific grain—it took too long and was inefficient.

The New Way (Measurement Test Algorithm):
The authors' new method skips the tedious piece-by-piece counting. Instead, it uses a direct measurement.

• Imagine you have a locked box with a single golden key inside.
• Instead of trying to feel the shape of the key through the box (which is hard and inaccurate), you use a special scanner (the Phase Estimation Algorithm) that tells you exactly what the key looks like.
• The algorithm prepares a "guess" (a quantum state) and then runs this scanner.
• If the scanner says, "Yes, this is the golden key!" (meaning the measurement result is zero), great!
• If it says, "No," the computer tweaks the knobs (the parameters) and tries again.

3. The "Tuning" Process

The computer doesn't just guess once. It runs a loop:

1. Guess: The computer creates a quantum state based on a set of adjustable settings (parameters).
2. Measure: It runs the "scanner" to see how close the guess is to the real answer.
3. Learn: A classical computer (the brain outside the quantum machine) looks at the result. If the "signal" wasn't perfect, it adjusts the knobs to make the next guess better.
4. Repeat: It keeps doing this until the probability of getting the right answer is as close to 100% as possible.

4. Why This is a Big Deal

The paper highlights three major advantages of this new method:

• It handles "Messy" Problems: Old methods struggled with complex, "dense" puzzles because they had to break them into too many tiny pieces. This new method can handle the whole messy puzzle at once without breaking it apart. It's like solving a jigsaw puzzle by looking at the whole picture rather than trying to sort every single piece into a separate pile first.
• It's Not Stuck by "Difficulty": Usually, some math problems are harder than others (measured by something called a "condition number"). Old quantum methods got slower and less accurate as the problem got harder. This new method says, "As long as we have enough memory (qubits) to distinguish the answer from the noise, the difficulty of the problem doesn't slow us down."
• It Gets More Accurate with More Tries: The accuracy of the answer depends on how many times you run the measurement. If you run the test more times (more "shots"), the answer gets sharper. The paper shows that the error shrinks predictably as you increase the number of measurements, reaching a very high level of precision.

5. The Catch: It Needs a "Perfect" Computer

The authors are very clear about one limitation: This algorithm requires a fault-tolerant quantum computer.

• Think of current quantum computers as "noisy" prototypes. They are great for experiments but make mistakes easily.
• This new algorithm is like a high-precision surgical tool; it needs a sterile, perfect operating room (a fault-tolerant computer) to work. It cannot be run on the current, noisy machines available today.

Summary

The paper presents a new "tuning" strategy for quantum computers to solve complex math equations. Instead of breaking the problem into tiny, slow-to-check pieces, it uses a direct measurement technique to "listen" for the correct answer. By repeatedly guessing, measuring, and adjusting, the computer can find the solution to even the most complex, messy equations, provided it has a perfect, error-free quantum machine to run on.

Technical Summary

1. Problem Statement

The paper addresses the challenge of solving linear systems of equations ($Mx = b$) on quantum computers, specifically targeting dense (non-sparse) matrices.

• Limitations of Existing Methods: Current Variational Quantum Algorithms (VQAs), such as the Variational Quantum Linear Solver (VQLS), rely on decomposing the cost function observable into Pauli strings. For dense matrices, the number of Pauli strings grows exponentially with the number of qubits. This leads to:
  • Excessive measurement overhead (shot noise accumulation).
  • Inefficiency due to the non-commutativity of Pauli operators.
  • Inability to handle general dense matrices within a reasonable timeframe.
• Readout Bottleneck: Standard amplitude encoding allows exponential storage capacity, but direct measurement of amplitudes requires exponential steps. VQAs attempt to bypass this by optimizing parameters, but they still struggle with the evaluation of the objective function for dense systems.

2. Methodology: The Measurement Test Algorithm

The authors propose a new variational algorithm called the Measurement Test Algorithm. Unlike traditional VQAs that minimize a cost function based on expectation values of known observables, this algorithm directly maximizes the target fidelity (the probability of projecting the system into the solution state) via quantum measurement.

Core Concepts

1. Reformulation as an Eigenvalue Problem:
   The linear system $Mx = b$ is transformed into finding the zero-eigenstate of a self-adjoint operator $A$:
   $$A = \hat{M}^\dagger (I - |b\rangle\langle b|) \hat{M}$$
   The solution $|y\rangle$ (from which $x$ is derived) satisfies $A|y\rangle = 0$.

2. Variational Ansatz:
   A parameterized quantum circuit $V(\alpha)$ prepares a trial state $|\psi(\alpha)\rangle = V(\alpha)|0\rangle$. The goal is to find parameters $\alpha$ such that $|\psi(\alpha)\rangle$ converges to the target eigenstate $|y\rangle$.

3. Quantum Measurement via Phase Estimation:
   Instead of measuring expectation values of Pauli strings, the algorithm implements a Von Neumann measurement of the observable $A$ using the Phase Estimation Algorithm (PEA):

   • An input register holds the ansatz state.
   • An output register (ancilla) is used to store the eigenvalues of $A$.
   • Controlled unitary operations $U = \exp(2\pi i A)$ are applied.
   • An inverse Quantum Fourier Transform (QFT) on the output register yields the eigenvalue $\lambda$ in binary representation.

4. Optimization Loop:

   • The algorithm runs the circuit $N$ times per iteration.
   • It counts the frequency $N_0$ of measuring the eigenvalue $\lambda = 0$ (represented as all zeros in the output register).
   • The merit function is the relative frequency $p(0) = N_0/N$, which estimates the fidelity $F_T = |\langle y | \psi(\alpha) \rangle|^2$.
   • A classical optimizer (specifically Rotosolve) adjusts the parameters $\alpha$ to maximize $p(0)$.

3. Key Contributions

The paper introduces three major advancements over previous VQAs:

1. Handling Dense Matrices:
   The algorithm does not rely on Pauli string decomposition. It treats the observable $A$ as a whole via Phase Estimation. This allows it to compute eigenvectors for dense matrices without the exponential overhead of Pauli terms.

2. Condition Number Independence (in terms of accuracy scaling):
   While the number of qubits required for the output register scales logarithmically with the condition number $\kappa$ ($m \ge 2 \log_2 \kappa$) to distinguish the zero eigenvalue from the second smallest, the accuracy of the solution is not limited by $\kappa$.

   • In contrast, methods like VQLS often suffer from accuracy degradation as $\kappa$ increases.
   • Here, accuracy is determined solely by the number of measurements (shots).

3. Heisenberg Scaling of Accuracy:
   The target fidelity $F_T = 1 - \epsilon$ scales with the number of measurements $N$ per iteration as:
   $$\epsilon \propto \frac{1}{N}$$
   This represents Heisenberg scaling (optimal scaling for quantum metrology), whereas standard sampling often scales as $1/\sqrt{N}$. The algorithm achieves this by directly estimating the probability of the specific outcome $\lambda=0$.

4. Results

The authors validated the algorithm through numerical simulations:

• Test Case: Dense, random, real-valued $16 \times 16$ matrices with non-vanishing determinants.
• Convergence: The target fidelity increased exponentially with the number of iterations until saturation.
• Accuracy Verification:
  • With $N = 2 \times 10^4$ shots, the fidelity saturated at $F_T \approx 1 - 2 \times 10^{-4}$.
  • Increasing shots to $N = 2 \times 10^6$ improved the fidelity to $F_T \approx 1 - 2 \times 10^{-6}$.
  • This confirmed the theoretical prediction that $\epsilon \approx a^2/N$ (where $a$ is a constant related to the optimizer's stopping criteria).
• Comparison with VQLS:
  • Simulations showed that the relative standard deviation of the estimator in the Measurement Test Algorithm remained constant regardless of the number of Pauli strings.
  • In contrast, the relative standard deviation for VQLS grew linearly with the number of Pauli strings, making VQLS impractical for dense matrices (requiring up to 256 Pauli strings for $16 \times 16$ systems).

5. Significance and Implications

• Fault-Tolerant Requirement: The algorithm requires fault-tolerant quantum computing to implement the Phase Estimation Algorithm (PEA) reliably. It is not designed for current Noisy Intermediate-Scale Quantum (NISQ) devices.
• New Paradigm: It proposes a "quantum algorithm without a classical analog" where the algorithm optimizes the expectation value of an unknown observable (the projector onto the solution state) rather than a known cost function.
• Scalability: By decoupling accuracy from the matrix condition number and avoiding Pauli decomposition, this method offers a viable path for solving high-dimensional linear systems with dense matrices, a task currently intractable for standard VQAs.
• Future Applications: The framework can be extended to other tasks involving the optimization of self-adjoint operators, such as finding ground state energies in the Variational Quantum Eigensolver (VQE).

Conclusion:
The Measurement Test Algorithm represents a significant theoretical step forward in quantum linear algebra. It overcomes the "Pauli string bottleneck" of current variational methods, offering a path to solve dense linear systems with accuracy limited only by measurement statistics (shot noise) rather than matrix properties, provided fault-tolerant hardware is available.