Quantum-Inspired Classical Algorithms for Solving Linear Feasibility Problems
Organizer
Speaker
Qian Zuo
Time
Saturday, January 11, 2025 2:00 PM - 3:00 PM
Venue
A3-3-301
Online
Zoom 293 812 9202
(BIMSA)
Abstract
We present a classical algorithm for linear feasibility problems $Ax \leq b$, where the input matrix $A$ is stored in a data structure suitable for QRAM-based state preparation. Specifically, given an matrix $A \in R^{m \times n}$ with a vector $b \in R^{m}$ which supports certain efficient $\ell_{2}$-norm importance sampling queries.
Then, after $T = O(\| A \|^{2}_{F} L^2 \log (1/\epsilon^2))$ steps of iteration, for some vector $x \in R^{n}$ satisfying $d(x_{T}, P) \leq \epsilon d(x, P)$, we can output a measurement of $|x \rangle$ in the computational basis and output an entry of $x$ with classical algorithms that run in $O (\| A \|^{6}_{F} \kappa^{6}_{F} L^6/ \epsilon^2 )$ time, where $L$ be a Hoffman constant and $\kappa_{F} = \| A \|_{F} \| A^{\dagger} \|$. Our work combines techniques from sketching algorithms and optimization with the quantum-inspired literature. This avenue shows promise for feasible implementations of classical linear inequality in quantum-inspired settings, offering a basis for comparison against future quantum computers.