An approximate quantum state preparation method is introduced, called the Walsh series loader (WSL). The WSL approximates quantum states defined by real-value functions of single real variables with a depth independent of the number of qubits. Two approaches are presented. The first one approximates the target quantum state by a Walsh series truncated at , where is the precision of the approximation in terms of infidelity. The circuit depth is also , the size is , and only one ancilla qubit is needed. The second method accurately represents quantum states with sparse Walsh series. The WSL loads -sparse Walsh series into qubits with a depth doubly sparse in and , the maximum number of bits with value 1 in the binary decomposition of the Walsh function indices. The associated quantum circuit approximates the sparse Walsh series up to an error with a depth , a size , and one ancilla qubit. In both cases, the protocol is a repeat-until-success procedure with a probability of success , giving an averaged total time of for the WSL and for the sparse WSL. Amplitude amplification can be used to reach a probability of success , modifying the quantum circuit size to and and the depth to and , respectively. Amplitude amplification reduces by a factor the total time dependence on but increases the size and depth of the associated quantum circuits, making them linearly dependent on . These protocols give overall efficient algorithms with no exponential scaling in any parameter. They can be generalized to any complex-value, multivariate, almost-everywhere-differentiable function. The repeat-until-success Walsh series loader is so far the only method that prepares a quantum state with a circuit depth and an averaged total time independent of the number of qubits.
Developing numerical methods to simulate efficiently nonlinear fluid dynamics on universal quantum computers is a challenging problem. In this paper, a generalization of the Madelung transform is defined to solve quantum relativistic charged fluid equations interacting with external electromagnetic forces via the Dirac equation. The Dirac equation is discretized into discrete-time quantum walks which can be efficiently implemented on universal quantum computers. A variant of this algorithm is proposed to implement simulations using current noisy intermediate scale quantum (NISQ) devices in the case of homogeneous external forces. High resolution (up to grid points) numerical simulations of relativistic and nonrelativistic hydrodynamical shocks on current IBM NISQs are performed with this algorithm. This paper demonstrates that fluid dynamics can be simulated on NISQs, and opens the door to simulating other fluids, including plasmas, with more general quantum walks and quantum automata.
Controlled operations are fundamental building blocks of quantum algorithms. Decomposing n-control-NOT gates (Cn(X)) into arbitrary single-qubit and CNOT gates, is a crucial but non-trivial task. This study introduces Cn(X) circuits outperforming previous methods in the asymptotic and non-asymptotic regimes. Three distinct decompositions are presented: an exact one using one borrowed ancilla with a circuit depth $$\Theta (\log {(n)}^{3})$$ , an approximating one without ancilla qubits with a circuit depth $${{{{{{{\mathcal{O}}}}}}}}(\log {(n)}^{3}\log (1/\epsilon ))$$ and an exact one with an adjustable-depth circuit which decreases with the number m≤n of ancilla qubits available as $${{{{{{{\mathcal{O}}}}}}}}(\log {(n/\lfloor m/2\rfloor )}^{3}+\log (\lfloor m/2\rfloor ))$$ . The resulting exponential speedup is likely to have a substantial impact on fault-tolerant quantum computing by improving the complexities of countless quantum algorithms with applications ranging from quantum chemistry to physics, finance and quantum machine learning.
11 April 2025 in ACM Transactions on Quantum Computing
Unitary and non-unitary diagonal operators are fundamental building blocks in quantum algorithms with applications in the resolution of partial differential equations, Hamiltonian simulations, the loading of classical data on quantum computers (quantum state preparation), and many others. In this paper, we introduce a general approach to implement unitary and non-unitary diagonal operators with efficient-adjustable-depth quantum circuits. The depth, i.e., the number of layers of quantum gates of the quantum circuit, is reducible with respect either to the width, i.e., the number of ancilla qubits, or to the accuracy between the implemented operator and the target one. While exact methods have an optimal exponential scaling either in terms of size, i.e., the total number of primitive quantum gates, or width, approximate methods prove to be efficient for the class of diagonal operators depending on smooth, at least differentiable, functions. Our approach is general enough to allow any method for diagonal operators to become adjustable-depth or approximate, decreasing the depth of the circuit by increasing its width or its approximation level. This feature offers flexibility and can match with the hardware limitations in coherence time or cumulative gate error. We illustrate these methods by performing quantum state preparation and non-unitary-real-space simulation of the diffusion equation. This simulation paves the way to efficient implementations of stochastic models useful in physics, chemistry, biology, image processing, and finance.
We present various results on the scheme introduced in a previous work, which is a quantum spatial-search algorithm on a two-dimensional (2D) square spatial grid, realized with a 2D Dirac discrete-time quantum walk (DQW) coupled to a Coulomb electric field centered on the the node to be found. In such a walk, the electric term acts as the oracle of the algorithm, and the free walk (i.e., without electric term) acts as the “diffusion” part, as it is called in Grover’s algorithm. The results are the following. First, we run long time simulations of this electric Dirac DQW, and observe that there is a second localization peak around the node marked by the oracle, reached in a time , where N is the number of nodes of the 2D grid, with a localization probability scaling as . This matches the state-of-the-art 2D-DQW search algorithms before amplitude amplification We then study the effect of adding noise on the Coulomb potential, and observe that the walk, especially the second localization peak, is highly robust to spatial noise, more modestly robust to spatiotemporal noise, and that the first localization peak is even highly robust to spatiotemporal noise.