2023/09/18 by Arthur G. Rattew, Patrick Rebentrost, Rattew, Arthur G. +1 · 3 citations
Computer Science · #Cloud Computing and Resource Management #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2309.09839
openalex publication_date 2023/09/18 · openalex created_date 2023/09/20 · openalex updated_date 2026/07/28
Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems. In this work, we present a framework for applying a general class of non-linear functions to the amplitudes of quantum states, with up-to an exponential improvement over the previous work. Our framework accepts a state preparation unitary (or block-encoding), specified as a quantum circuit, defining an N-dimensional quantum state. We then construct a diagonal block-encoding of the amplitudes of the quantum state, building on and simplifying previous work. Techniques from the QSVT literature are then used to process this block-encoding. The source of our exponential speedup comes from the quantum analog of importance sampling. We then derive new error-bounds relevant for end-to-end applications, giving the error in terms of ℓ2-norm error. We demonstrate the power of this framework with four key applications. First, our algorithm can apply the important function \tanh(x) to the amplitudes of an arbitrary quantum state with at most an ℓ2-norm error of ε, with worst-case query complexity of O(log(N/ε)), in comparison to the O(√(N)log(N/ε)) of prior work. Second, we present an algorithm solving a new formulation of maximum finding in the unitary input model. Third, we prove efficient end-to-end complexities in applying a number of common non-linear functions to arbitrary quantum states. Finally, we generalize and unify existing quantum arithmetic-free state-preparation techniques. Our work provides an important and efficient algorithmic building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.