Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

Approximating the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -th spectral gap <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi mathvariant="normal">&amp;#x0394;</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>&amp;#x03BB;</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>&amp;#x2212;</mml:mo> <mml:msub> <mml:mi>&amp;#x03BB;</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> </mml:math> and the corresponding midpoint <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>&amp;#x03BC;</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mrow> <mml:msub> <mml:mi>&amp;#x03BB;</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>&amp;#x03BB;</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:mn>2</mml:mn> </mml:mfrac> </mml:math> of an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>N</mml:mi> <mml:mo>&amp;#x00D7;</mml:mo> <mml:mi>N</mml:mi> </mml:math> Hermitian matrix with eigenvalues <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>&amp;#x03BB;</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>&amp;#x2265;</mml:mo> <mml:msub> <mml:mi>&amp;#x03BB;</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>&amp;#x2265;</mml:mo> <mml:mo>&amp;#x2026;</mml:mo> <mml:mo>&amp;#x2265;</mml:mo> <mml:msub> <mml:mi>&amp;#x03BB;</mml:mi> <mml:mi>N</mml:mi> </mml:msub> </mml:math> , is an important special case of the eigenproblem with numerous applications in science and engineering. In this work, we present a quantum algorithm which approximates these values up to additive error <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>&amp;#x03F5;</mml:mi> <mml:msub> <mml:mi mathvariant="normal">&amp;#x0394;</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> using a logarithmic number of qubits. Notably, in the QRAM model, its total complexity (queries and gates) is bounded by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mfrac> <mml:msup> <mml:mi>N</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mrow> <mml:msup> <mml:mi>&amp;#x03F5;</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:msubsup> <mml:mi mathvariant="normal">&amp;#x0394;</mml:mi> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> </mml:mrow> </mml:mfrac> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">p</mml:mi> <mml:mi mathvariant="normal">o</mml:mi> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">y</mml:mi> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">o</mml:mi> <mml:mi mathvariant="normal">g</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>,</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:msub> <mml:mi mathvariant="normal">&amp;#x0394;</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:mfrac> <mml:mo>,</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>&amp;#x03F5;</mml:mi> </mml:mfrac> <mml:mo>,</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>&amp;#x03B4;</mml:mi> </mml:mfrac> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>&amp;#x03F5;</mml:mi> <mml:mo>,</mml:mo> <mml:mi>&amp;#x03B4;</mml:mi> <mml:mo>&amp;#x2208;</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:math> are the accuracy and the failure probability, respectively. For large gaps <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi mathvariant="normal">&amp;#x0394;</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> , this provides a speed-up against the best-known complexities of classical algorithms, namely, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>&amp;#x03C9;</mml:mi> </mml:mrow> </mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">p</mml:mi> <mml:mi mathvariant="normal">o</mml:mi> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">y</mml:mi> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">o</mml:mi> <mml:mi mathvariant="normal">g</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>,</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn>