An improved quantum-inspired algorithm for linear regression

Abstract

We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18], when the input matrix <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>A</mml:mi></mml:math> is stored in a data structure applicable for QRAM-based state preparation.Namely, suppose we are given an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>A</mml:mi><mml:mo>&amp;#x2208;</mml:mo><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="double-struck">C</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>m</mml:mi><mml:mo>&amp;#x00D7;</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:msup></mml:math> with minimum non-zero singular value <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&amp;#x03C3;</mml:mi></mml:math> which supports certain efficient <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>&amp;#x2113;</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:math>-norm importance sampling queries, along with a <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>b</mml:mi><mml:mo>&amp;#x2208;</mml:mo><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="double-struck">C</mml:mi></mml:mrow><mml:mi>m</mml:mi></mml:msup></mml:math>. Then, for some <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>x</mml:mi><mml:mo>&amp;#x2208;</mml:mo><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="double-struck">C</mml:mi></mml:mrow><mml:mi>n</mml:mi></mml:msup></mml:math> satisfying <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mi>x</mml:mi><mml:mo>&amp;#x2013;</mml:mo><mml:msup><mml:mi>A</mml:mi><mml:mo>+</mml:mo></mml:msup><mml:mi>b</mml:mi><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mo>&amp;#x2264;</mml:mo><mml:mi>&amp;#x03B5;</mml:mi><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:msup><mml:mi>A</mml:mi><mml:mo>+</mml:mo></mml:msup><mml:mi>b</mml:mi><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo></mml:math>, we can output a measurement of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>x</mml:mi><mml:mo fence="false" stretchy="false">&amp;#x27E9;</mml:mo></mml:math> in the computational basis and output an entry of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>x</mml:mi></mml:math> with classical algorithms that run in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">&amp;#x007E;</mml:mo></mml:mover></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo></mml:mrow><mml:mfrac><mml:mrow><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mi>A</mml:mi><mml:msubsup><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">F</mml:mi></mml:mrow></mml:mrow><mml:mn>6</mml:mn></mml:msubsup><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mi>A</mml:mi><mml:msup><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mn>6</mml:mn></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mi>&amp;#x03C3;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>12</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mi>&amp;#x03B5;</mml:mi><mml:mn>4</mml:mn></mml:msup></mml:mrow></mml:mfrac><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo></mml:mrow></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">&amp;#x007E;</mml:mo></mml:mover></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo></mml:mrow><mml:mfrac><mml:mrow><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mi>A</mml:mi><mml:msubsup><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">F</mml:mi></mml:mrow></mml:mrow><mml:mn>6</mml:mn></mml:msubsup><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mi>A</mml:mi><mml:msup><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mn>2</mml:mn></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mi>&amp;#x03C3;</mml:mi><mml:mn>8</mml:mn></mml:msup><mml:msup><mml:mi>&amp;#x03B5;</mml:mi><mml:mn>4</mml:mn></mml:msup></mml:mrow></mml:mfrac><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo></mml:mrow></mml:math> time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:mrow><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mi>A</mml:mi><mml:msup><mml:mo fence="false" stretchy="false">&amp;#x2016;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>16</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mi>&amp;#x03C3;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>16</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mi>&amp;#x03B5;</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:mfrac></mml:math> [Chia, Gilyén, Li, Lin, Tang, and Wang, STOC'20]. As a consequence, we show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting and related settings. Our work applies techniques from sketching algorithms and optimization to the quantum-inspired literature. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired settings, for comparison against future quantum computers.