An efficient quantum algorithm for preparation of uniform quantum superposition states

Abstract

Quantum state preparation involving a uniform superposition over a non-empty subset of $n$-qubit computational basis states is an important and challenging step in many quantum computation algorithms and applications. In this work, we address the problem of preparation of a uniform superposition state of the form $|\Psi ⟩=\frac{1}{\sqrt{M}}{\sum }_{j=0}^{M-1}|j⟩$, where $M$ denotes the number of distinct states in the superposition state and $2\le M\le 2^n$. We show that the superposition state $|\Psi ⟩$ can be efficiently prepared with a gate complexity and circuit depth of only $O({\log }_{2}M)$ for all $M$. This demonstrates an exponential reduction in gate complexity in comparison to other existing approaches in the literature for the general case of this problem. Another advantage of the proposed approach is that it requires only $n=\ceil{\log_2~M}$ qubits. Furthermore, neither ancilla qubits nor any quantum gates with multiple controls are needed in our approach for creating the uniform superposition state $|\Psi ⟩$. It is also shown that a broad class of nonuniform superposition states that involve a mixture of uniform superposition states can also be efficiently created with the same circuit configuration that is used for creating the uniform superposition state $|\Psi ⟩$ described earlier, but with modified parameters.

26 pages. An Author Contributions section was added

References in corpus (4)

• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Quantum Data Fitting
• Quantum-state preparation with universal gate decompositions

Cited by in corpus (9)

• Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
• Jet Discrimination with Quantum Complete Graph Neural Network
• Permutation-equivariant quantum convolutional neural networks
• A quantum approach for optimal control
• Efficient quantum algorithm for weighted partial sums and numerical integration
• Fast Quantum Amplitude Encoding of Typical Classical Data
• Encodings of the weighted MAX k-CUT on qubit systems
• Benincasa-Dowker-Glaser causal set actions by quantum counting
• Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions