Source-linked AI summary
Black-box quantum state preparation without arithmetic
Yuval R. Sanders, Guang Hao Low, Artur Scherer, Dominic W. Berry
TL;DR
Grover’s black-box state preparation uses arithmetic, including arcsine calculations that contribute substantially to its cost. This paper replaces that step with an inequality test and reports 286-to-375-fold improvement for the precisions considered, with expected applications to quantum-walk and LCU algorithms.
Problem
Grover’s black-box state preparation requires arcsine calculations, a major contributor to its complexity.
Source: p. 1Method
The method replaces the rotation procedure with an inequality test against a superposition of possible oracle outputs, then uses amplitude amplification to transduce values into amplitudes.
Source: pp. 1, 2, 4Results
The reported complexity improvement is a factor of 286 to 375 for the precisions considered, and it increases with precision.
Source: p. 4Takeaways & Limitations
The authors expect the approach to replace Grover’s method in quantum-walk operators and LCU, with possible benefits for quantum-chemistry algorithms.
Source: p. 4Finite-precision approximation of the oracle coefficients adds error that scales as 2^-n.
Source: p. 4
Abstract
from arXiv · showhide
Black-box quantum state preparation is an important subroutine in many quantum algorithms. The standard approach requires the quantum computer to do arithmetic, which is a key contributor to the complexity. Here we present a new algorithm that avoids arithmetic. We thereby reduce the number of gates by a factor of 286-374 over the best prior work for realistic precision; the improvement factor increases with the precision. As quantum state preparation is a crucial subroutine in many approaches to simulating physics on a quantum computer, our new method brings useful quantum simulation closer to reality.