Low depth algorithms for quantum amplitude estimation (2022)

We design and analyze two new low depth algorithms for amplitude estimation (AE) achieving an optimal tradeoff between the quantum speedup and circuit depth. For <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B2;</mml:mi><mml:mo>&#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>, our algorithms require <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi><mml:mo>=</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>O</mml:mi><mml:mo stretchy="false">&#x007E;</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:msup><mml:mi>&#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>&#x03B2;</mml:mi></mml:mrow></mml:msup></mml:mfrac><mml:mo stretchy="false">)</mml:mo></mml:math> oracle calls and require the oracle to be called sequentially <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>D</mml:mi><mml:mo>=</mml:mo><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:msup><mml:mi>&#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>&#x2212;</mml:mo><mml:mi>&#x03B2;</mml:mi></mml:mrow></mml:msup></mml:mfrac><mml:mo stretchy="false">)</mml:mo></mml:math> times to perform amplitude estimation within additive error <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03F5;</mml:mi></mml:math>. These algorithms interpolate between the classical algorithm <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo stretchy="false">(</mml:mo><mml:mi>&#x03B2;</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:math> and the standard quantum algorithm (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B2;</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:math>) and achieve a tradeoff <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi><mml:mi>D</mml:mi><mml:mo>=</mml:mo><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:msup><mml:mi>&#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math>. These algorithms bring quantum speedups for Monte Carlo methods closer to realization, as they can provide speedups with shallower circuits.The first algorithm (Power law AE) uses power law schedules in the framework introduced by Suzuki et al \cite{S20}. The algorithm works for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B2;</mml:mi><mml:mo>&#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> and has provable correctness guarantees when the log-likelihood function satisfies regularity conditions required for the Bernstein Von-Mises theorem. The second algorithm (QoPrime AE) uses the Chinese remainder theorem for combining lower depth estimates to achieve higher accuracy. The algorithm works for discrete <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B2;</mml:mi><mml:mo>=</mml:mo><mml:mi>q</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>k</mml:mi></mml:math> where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi><mml:mo>&#x2265;</mml:mo><mml:mn>2</mml:mn></mml:math> is the number of distinct coprime moduli used by the algorithm and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn><mml:mo>&#x2264;</mml:mo><mml:mi>q</mml:mi><mml:mo>&#x2264;</mml:mo><mml:mi>k</mml:mi><mml:mo>&#x2212;</mml:mo><mml:mn>1</mml:mn></mml:math>, and has a fully rigorous correctness proof. We analyze both algorithms in the presence of depolarizing noise and provide numerical comparisons with the state of the art amplitude estimation algorithms.