Efficient quantum state preparation with Walsh series

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 $n$ of qubits. Two approaches are presented. The first one approximates the target quantum state by a Walsh series truncated at $O(1/\sqrt{\ensuremath{\epsilon}})$, where $\ensuremath{\epsilon}$ is the precision of the approximation in terms of infidelity. The circuit depth is also $O(1/\sqrt{\ensuremath{\epsilon}})$, the size is $O(n+1/\sqrt{\ensuremath{\epsilon}})$, and only one ancilla qubit is needed. The second method accurately represents 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 $\ensuremath{\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 procedure with a probability of success $P=\mathrm{\ensuremath{\Theta}}(\ensuremath{\epsilon})$, giving an averaged total time of $O(1/{\ensuremath{\epsilon}}^{3/2})$ for the WSL and $O(sk/\ensuremath{\epsilon})$ for the sparse WSL. Amplitude amplification can be used to reach a probability of success $P=\mathrm{\ensuremath{\Theta}}(1)$, modifying the quantum circuit size to $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+1/\sqrt{\ensuremath{\epsilon}})/\sqrt{\ensuremath{\epsilon}})$ and $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+sk)/\sqrt{\ensuremath{\epsilon}})$ and the depth to $O([log{(n)}^{3}+1/\sqrt{\ensuremath{\epsilon}}]/\sqrt{\ensuremath{\epsilon}})$ and $O([log{(n)}^{3}+sk]/\sqrt{\ensuremath{\epsilon}})$, respectively. Amplitude amplification reduces by a factor $O(1/\sqrt{\ensuremath{\epsilon}})$ the total time dependence on $\ensuremath{\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-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.