Efficient Sparse State Preparation via Quantum Walks
arXiv:2405.20273 · doi:10.1038/s41534-025-01093-y
Abstract
Continuous-time quantum walks (CTQWs) on dynamic graphs, referred to as dynamic CTQWs, are a recently introduced universal model of computation that offers a new paradigm in which to envision quantum algorithms. In this work we develop an algorithm that converts single-edge and self-loop dynamic CTQWs to the gate model of computation. We use this mapping to introduce an efficient sparse quantum state preparation framework based on dynamic CTQWs. Our approach utilizes combinatorics techniques such as minimal hitting sets, minimum spanning trees, and shortest Hamiltonian paths to reduce the number of controlled gates required to prepare sparse states. We show that our framework encompasses the current state of the art ancilla free sparse state preparation method by reformulating this method as a CTQW. This CTQW-based framework offers an alternative to the uniformly controlled rotation method used by Qiskit by requiring fewer CX gates when the target state has a polynomial number of non-zero amplitudes.
Comments are welcome!
References in corpus (10)
- Quantum algorithm for solving linear systems of equations
- Logical quantum processor based on reconfigurable atom arrays
- Universal computation by quantum walk
- Spatial search by quantum walk
- Synthesis of Quantum Logic Circuits
- Quantum-state preparation with universal gate decompositions
- Continuous-Time Quantum Walks on Dynamic Graphs
- Performance Analysis of Multi-Angle QAOA for p > 1
- Quantum approximate optimization algorithm with random and subgraph phase operators
- Implementing Quantum Gates Using Length-3 Dynamic Quantum Walks