# Spacetime-Efficient Low-Depth Quantum State Preparation with Applications

arXiv: https://arxiv.org/abs/2303.02131 · HTML: https://mlsanity.com/paper/2303.02131/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 68 references that are in the map.
- First posted on arXiv 3 Mar 2023.

## Builds on (most cited first, 15 of 15)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Large Kernel Matters -- Improve Semantic Segmentation by Global Convolutional Network](https://mlsanity.com/paper/1703.02719/) (2017)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Scaling Up Your Kernels to 31x31: Revisiting Large Kernel Design in CNNs](https://mlsanity.com/paper/2203.06717/) (2022)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [A divide-and-conquer algorithm for quantum state preparation](https://mlsanity.com/paper/2008.01511/) (2020)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)

## Built on by (most cited first, 2 of 2)

- [Graph Neural Networks on Quantum Computers](https://mlsanity.com/paper/2405.17060/) (2024)
- [Data is often loadable in short depth: Quantum circuits from tensor networks for finance, images, fluids, and proteins](https://mlsanity.com/paper/2309.13108/) (2023)

## Abstract (arXiv)

We propose a novel deterministic method for preparing arbitrary quantum states. When our protocol is compiled into CNOT and arbitrary single-qubit gates, it prepares an N-dimensional state in depth O(log(N)) and spacetime allocation (a metric that accounts for the fact that oftentimes some ancilla qubits need not be active for the entire circuit) O(N), which are both optimal. When compiled into the H,S,T,CNOT gate set, we show that it requires asymptotically fewer quantum resources than previous methods. Specifically, it prepares an arbitrary state up to error ε with optimal depth of O(log(N) + log (1/ε)) and spacetime allocation O(Nlog(log(N)/ε)), improving over O(log(N)log(log (N)/ε)) and O(Nlog(N/ε)), respectively. We illustrate how the reduced spacetime allocation of our protocol enables rapid preparation of many disjoint states with only constant-factor ancilla overhead -- O(N) ancilla qubits are reused efficiently to prepare a product state of w N-dimensional states in depth O(w + log(N)) rather than O(wlog(N)), achieving effectively constant depth per state. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations. We provide quantum circuit descriptions of our protocol, detailed pseudocode, and gate-level implementation examples using Braket.