Abstract Black-box quantum state preparation is a fundamental building block for many higher-level quantum algorithms. The basic task of black-box state preparation is to transduce the data encoded as computational basis of quantum state into the amplitude. In the present work, we address the problem of transducing the reciprocal of the data, not the data itself into the amplitude, which is called the inverse-coefficient problem. This algorithm can be used directly as a subroutine in the matrix inversion algorithms. Furthermore, we extend this approach to address the more general nonlinear-coefficient problem in black-box state preparation. Our algorithm is based on the technique of inequality test. It can greatly relieve the need to do quantum arithmetic and the error is only resulted from the truncated error of binary string. The present algorithms enrich the algorithm library of black-box quantum state preparation and will be useful ingredients of quantum algorithm to implement non-linear quantum state transformations.
Abstract Black-box quantum state preparation is a fundamental building block for many higher-level quantum algorithms. The basic task of black-box state preparation is to transduce the data encoded as computational basis of quantum state into the amplitude. In the present work, we address the problem of transducing the reciprocal of the data, not the data itself into the amplitude, which is called the inverse-coefficient problem. This algorithm can be used directly as a subroutine in the matrix inversion algorithms. Furthermore, we extend this approach to address the more general nonlinear-coefficient problem in black-box state preparation. Our algorithm is based on the technique of inequality test. It can greatly relieve the need to do quantum arithmetic and the error is only resulted from the truncated error of binary string. The present algorithms enrich the algorithm library of black-box quantum state preparation and will be useful ingredients of quantum algorithm to implement non-linear quantum state transformations.
Quantum state preparation is an important ingredient for other higher-level quantum algorithms, such as Hamiltonian simulation, or for loading distributions into a quantum device to be used e.g. in the context of optimization tasks such as machine learning. Starting with a generic "black box" method devised by Grover in 2000, which employs amplitude amplification to load coefficients calculated by an oracle, there has been a long series of results and improvements with various additional conditions on the amplitudes to be loaded, culminating in Sanders et al.'s work which avoids almost all arithmetic during the preparation stage.In this work, we construct an optimized black box state loading scheme with which various important sets of coefficients can be loaded significantly faster than in O(N) rounds of amplitude amplification, up to only O(1) many. We achieve this with two variants of our algorithm. The first employs a modification of the oracle from Sanders et al., which requires fewer ancillas ( log2g vs g+2 in the bit precision g ), and fewer non-Clifford operations per amplitude amplification round within the context of our algorithm. The second utilizes the same oracle, but at slightly increased cost in terms of ancillas ( g+log2g ) and non-Clifford operations per amplification round. As the number of amplitude amplification rounds enters as multiplicative factor, our black box state loading scheme yields an up to exponential speedup as compared to prior methods. This speedup translates beyond the black box case.
Black-box quantum-state preparation is a variant of quantum-state preparation where we want to construct an n-qubit state ∣ψc⟩∝∑xc(x)∣x⟩ with the amplitudes c(x) given as a (quantum) oracle. This variant is particularly useful when the quantum state has a short and simple classical description. We use recent techniques, namely quantum signal processing (QSP) and quantum singular value transform (QSVT), to construct a new algorithm that prepares ∣ψc⟩ without the need to carry out coherent arithmetic. We then compare our result with current state-of-the-art algorithms, showing that a QSVT-based approach achieves comparable results.
Quantum algorithm involves the manipulation of amplitudes and computational basis, of which manipulating basis is largely a quantum analogue of classical computing that is always a major contributor to the complexity. In order to make full use of quantum mechanical speedup, more transformation should be implemented on amplitudes. Here we propose the notion of quantum amplitude arithmetic (QAA) that intent to evolve the quantum state by performing arithmetic operations on amplitude. Based on the basic design of multiplication and addition operations, QAA can be applied to solve the black-box quantum state preparation problem and the quantum linear system problem with fairly low complexity, and evaluate nonlinear functions on amplitudes directly. QAA is expected to find applications in a variety of quantum algorithms.
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.
Quantum state preparation is an important class of quantum algorithms that is employed as a black-box subroutine in many algorithms, or used by itself to generate arbitrary probability distributions. We present a novel state preparation method that utilizes less quantum computing resource than the existing methods. Two variants of the algorithm with different emphases are introduced. One variant uses fewer qubits and no controlled gates, while the other variant potentially requires fewer gates overall. A general analysis is given to estimate the number of qubits necessary to achieve a desired precision in the amplitudes of the computational basis states. The validity of the algorithm is demonstrated using a prototypical problem of generating Ising model spin configurations according to its Boltzmann distribution.
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(Nlog(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.