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 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 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.
Quantum state preparation is a fundamental primitive in quantum algorithms for encoding classical data into quantum amplitudes. We compare the cost of preparing general n-qubit states with real amplitudes using two common paradigms: rotation-based methods, based on controlled rotations, and sampling-based methods, based on a structured representation of the target state. Although these approaches are often theoretically compared using CNOT count and T-count, their relative performance in total gate count remains less well understood practically. We compare representative rotation-based and sampling-based methods using T-count and total gate count, and analyze how compilation overhead affects their relative performance. We also develop a software package for compiling state preparation circuits, designed as a practical subroutine for more general quantum computations. Numerical experiments on resource states and quantum states related to quantum chemistry, condensed matter physics, and simulation via Magnus expansion over a range of target accuracies ε support the analysis. Our results show that sampling-based methods achieve asymptotically lower T-count and retain an overall advantage after accounting for total gate count and compilation overhead.
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 computing promises to provide exponential speed-ups to certain classes of problems. In many such algorithms, a classical vector b is encoded in the amplitudes of a quantum state ∣b⟩. However, efficiently preparing ∣b⟩ is known to be a difficult problem because an arbitrary state of Q qubits generally requires approximately 2Q entangling gates, which results in significant decoherence on today's noisy intermediate-scale quantum (NISQ) computers. We present a deterministic (nonvariational) algorithm that allows us to flexibly reduce the quantum resources required for state preparation in an entanglement-efficient manner. Although this comes at the expense of reduced theoretical fidelity, actual fidelities on current NISQ computers might actually be higher due to reduced decoherence. We show this to be true for various cases of interest, such as the normal and log-normal distributions. For low-entanglement states, our algorithm can prepare states with more than an order of magnitude fewer entangling gates as compared with isometric decomposition.
Quantum state preparation is the process of producing a target quantum state that will be used as the input to a quantum circuit. Many quantum algorithms require an input state where amplitudes, phases, or basis probabilities encode problem data, and the cost of preparing this state can be significant in gate count and circuit depth. This review summarizes common goals, assumptions, and methods for quantum state preparation, with emphasis on preparing states from classical vectors, probability distributions, and feature data used in quantum machine learning. We organize approaches by the information they load and by the resources they require, including gate count, circuit depth, qubit overhead, and classical preprocessing. It also compares exact and approximate preparation procedures, and discusses how precision targets affect cost. The review highlights links between families of methods, typical sources of resource estimates, and criteria that help match a preparation method to a task and hardware constraints.
The Box-Muller transform is a widely used method to generate Gaussian samples from uniform samples. Quantum amplitude encoding methods encode the multi-variate normal distribution in the amplitudes of a quantum state. This work presents the Quantum Box-Muller transform which creates a superposition of binary-encoded grid points representing the multi-variate normal distribution. The gate complexity of our method depends on quantum arithmetic operations and, using a specific set of known implementations, the complexity is quadratic in the number of qubits. We apply our method to Monte-Carlo integration, in particular to the estimation of the expectation value of a function of Gaussian random variables. Our method implies that the state preparation circuit used multiple times in amplitude estimation requires only quantum arithmetic circuits for the grid points and the function, in addition to a single controlled rotation. We show how to provide the expectation value estimate with an error that is exponentially small in the number of qubits, similar to the amplitude-encoding setting with error-free encoding.