Linear Order Matrix Inversion Method with Help from Quantum Searching Algorithm

Atsushi MiyauchiarXiv 2001 · DOI · arXiv

Abstract

This paper presents a novel matrix inversion method utilizing a quantum searching algorithm. By searching and evaluating a massive Hilbert space through sequential dimensional reduction, the method achieves a total iteration count proportional to the number of unknown variables ($O(n)$). This approach offers a potential path to solving large-scale linear equations with high probability and significantly greater efficiency than classical algorithms, which typically scale cubically ($O(n^3)$).

Introduction

Matrix inversion is a fundamental operation in computational science, underpinning critical applications in weather forecasting, aerodynamics, finance, and molecular biology. Despite its ubiquity, the computational cost of solving large systems of linear equations remains a significant bottleneck. The standard classical approach, Gaussian elimination, requires operations proportional to the cube of the number of variables ($n^3$). As problem sizes grow, this cubic scaling becomes prohibitively expensive.

While quantum computing promises "quantum parallelism," applying quantum searching (such as Grover’s algorithm) naively to find a solution in a multi-dimensional space often results in exponential complexity ($M^n$, where $M$ is the numerical precision). This paper proposes a "Dimensional Reduction" strategy that harnesses quantum searching to achieve linear scaling, effectively bypassing the exponential trap.

The Dimensional Reduction Strategy

The core innovation of this method is the "box in a box" strategy. Rather than attempting to search the entire $n$-dimensional Hilbert space simultaneously—which leads to the aforementioned exponential growth—the algorithm proceeds sequentially, reducing the problem's dimensionality one step at a time.

Sequential Search and BBHT

The problem $Ax + b = 0$ is mapped onto a quantum state. The algorithm begins by identifying all possible values that satisfy the first row of the matrix equation. This initial step reduces the search space from $n$ dimensions to $n-1$.

Because this first step identifies a subspace of multiple possible solutions rather than a single point, the method employs the BBHT algorithm (a variant of Grover’s search developed by Boyer, Brassard, Høyer, and Tapp). BBHT is uniquely suited for this task as it can efficiently find solutions even when the number of valid targets is unknown or multiple.

Iterative Refinement and Garbage Erasure

This process is repeated for each subsequent row. Each iteration "peels away" a dimension of the search space until the unique solution is isolated. To maintain the integrity of the quantum state and ensure the process is reversible, the algorithm utilizes "backward operations" (Bennett’s trick) to erase intermediate "garbage" data generated during the calculation of each row. This ensures that the quantum register remains clean for subsequent steps.

Performance and Complexity

Linear Scaling

The transition from searching a high-dimensional space all at once to searching it one dimension at a time is the key to the algorithm's efficiency. While a holistic search scales as $O(\sqrt{M^n})$, the sequential approach turns the complexity into a summation ($n \times \sqrt{M}$).

In this model, $M$ represents the number of possible values for each variable (determined by the required bit-precision). Once the precision is fixed, $\sqrt{M}$ becomes a constant factor, resulting in a total iteration count of approximately: $$\frac{\pi}{4} n \sqrt{M}$$

The Crossover Point

Numerical estimations suggest that for a standard 32-bit precision system, this quantum method would begin to outperform classical $O(n^3)$ algorithms at a matrix size of approximately $n = 321$. The total operational count for the entire computation is estimated at $2n(51,471 + n)$, where the $n^2$ term accounts for the necessity of calculating inner products.

Reliability

The author demonstrates through mathematical lemmas that the success probability of the algorithm remains high even for massive systems. The probability is defined as $(1 - 1/M)^n$. For 32-bit precision, the algorithm maintains a success rate of over 93% even when dealing with a billion variables ($n = 10^9$).

Limitations and Future Outlook

While the theoretical framework is robust, several challenges remain for practical implementation:

  1. Oracle Construction: The design of the "quantum oracle"—the circuit component that verifies if an equation is satisfied—is a significant engineering hurdle not fully detailed in this proposal.
  2. Hardware Constraints: The efficiency of the algorithm depends on the speed of quantum gates. Significant improvements in quantum hardware are required to compete with the high clock speeds of modern classical processors.
  3. Error and Decoherence: The impact of physical quantum errors and decoherence on the success probability in a real-world, noisy environment requires further investigation.
  4. Matrix Generalization: The current proof for the dimensional reduction strategy assumes conditions similar to diagonal dominance. Extending this to more general or ill-conditioned matrices is a primary target for future research.

Conclusion

By reimagining matrix inversion as a sequential quantum search problem, this method provides a theoretical framework to break the $O(n^3)$ barrier. The linear scaling of iteration steps relative to the number of variables represents a significant leap forward in quantum algorithmic design, offering a potential solution for the massive linear systems of the future.

Summary updated

Abstract

Presented here is a matrix inversion method utilizing quantum searching algorithm. In this method, huge Hilbert space as a whole spanned by myriad of eigen states is searched and evaluated efficiently by sequential reduction in dimension one by one. Total iteration steps required for search are proportional to the number of unknown variables. Our method could solve very large linear equations with sufficiently high probability faster than any existing classical algorithms, which roughly depends on the cube of unknown variables.
BibTeX
@misc{miyauchi2001linear,
  author = {Atsushi Miyauchi},
  title = {{Linear Order Matrix Inversion Method with Help from Quantum Searching Algorithm}},
  year = {2001},
  eprint = {quant-ph/0109131},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/quant-ph/0109131},
}
Figure