  A new approximate Quantum State Preparation (QSP) method is introduced,
called the Walsh Series Loader (WSL). The WSL approximates quantum states
defined by real-valued functions of single real variables with a depth
independent of the number $n$ of qubits. Two approaches are presented: the
first one approximates the target quantum state by a Walsh Series truncated at
order $O(1/\sqrt{\epsilon})$, where $\epsilon$ is the precision of the
approximation in terms of infidelity. The circuit depth is also
$O(1/\sqrt{\epsilon})$, the size is $O(n+1/\sqrt{\epsilon})$ and only one
ancilla qubit is needed. The second method represents accurately quantum states
with sparse Walsh series. The WSL loads $s$-sparse Walsh Series into $n$-qubits
with a depth doubly-sparse in $s$ and $k$, 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
$\epsilon$ with a depth $O(sk)$, a size $O(n+sk)$ and one ancilla qubit. In
both cases, the protocol is a Repeat-Until-Success (RUS) procedure with a
probability of success $P=\Theta(\epsilon)$, giving an averaged total time of
$O(1/\epsilon^{3/2})$ for the WSL (resp. $O(sk/\epsilon)$ for the sparse WSL).
Amplitude amplification can be used to reduce by a factor
$O(1/\sqrt{\epsilon})$ the total time dependency with $\epsilon$ but increases
the size and depth of the associated quantum circuits, making them linearly
dependent on $n$. These protocols give overall efficient algorithms with no
exponential scaling in any parameter. They can be generalized to any
complex-valued, multi-variate, almost-everywhere-differentiable function. The
Repeat-Until-Success Walsh Series Loader is so far the only method which
prepares a quantum state with a circuit depth and an averaged total time
independent of the number of qubits.
