Quantum State Preparation using Adaptive Circuits
Daan In de Braekt

Abstract:
Quantum state preparation (QSP) plays a pivotal role in quantum computing, enabling quantum algorithms to process classical data efficiently. Determining the complexity of QSP is crucial for understanding whether quantum algorithms can offer exponential speed-ups over their classical counterparts. Recent advances in adaptive quantum circuits – circuits that are augmented with mid-circuit measurements and classical feedback – suggest potential advantages in reducing circuit depth, which is especially relevant given the high error rates of current quantum hardware. Previous work has demonstrated that adaptive circuits can have an exponentially higher success probability over non-adaptive counterparts in preparing specific quantum states, such as the GHZ-state and the W-state. However, it remains an open question whether these advantages extend to general QSP algorithms, and, in particular, to sparse QSP, where only a small subset of amplitudes are non-zero.
This thesis systematically examines the trade-offs between adaptive and non-adaptive circuits for both general and sparse QSP. We analyse two QSP approaches: (1) UCG-based QSP, which utilizes uniformly controlled gates, and (2) unary-based QSP, which encodes data in a unary representation before transformation. By leveraging known speed-ups for adaptive implementations of important multi-qubit gates, such as the Fanout-gate and the OR-gate, we assess the conditions under which adaptive circuits provide an exponential advantage. Our results indicate that adaptive circuits significantly improve success probabilities for both general and sparse QSP, particularly in regimes where qubit idling errors dominate.
Using empirical error rates from current quantum processors, we derive lower bounds on the number of qubits required to observe an adaptive advantage. While non-adaptive circuits assuming all-to-all connectivity generally perform well for preparing quantum states with less than 1000 qubits, adaptive circuits demonstrate substantial improvements when compared to non-adaptive circuits constrained to a 2D grid topology. These findings suggest that adaptivity could help in enabling efficient quantum state preparation, particularly for near-term quantum devices with limited connectivity.