Efficient Sparse State Preparation via Quantum Walks

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 (34)

• A variational eigenvalue solver on a quantum processor
• 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
• qubit-ADAPT-VQE: An adaptive algorithm for constructing hardware-efficient ansatze on a quantum processor
• Quantum-state preparation with universal gate decompositions
• Robust data encodings for quantum classifiers
• Quantum speedup of Monte Carlo methods
• Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
• Experimental Two-dimensional Quantum Walk on a Photonic Chip
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Experimental Perfect Quantum State Transfer
• Efficient quantum algorithms for $GHZ$ and $W$ states, and implementation on the IBM quantum computer
• Deterministic Preparation of Dicke States
• Quantum Vision Transformers
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Linear-depth quantum circuits for multiqubit controlled gates
• Efficient State Preparation for Quantum Amplitude Estimation
• Quantum Circuits for Sparse Isometries
• Short-Depth Circuits for Dicke State Preparation
• Double sparse quantum state preparation
• Fault-Tolerant One-Bit Addition with the Smallest Interesting Colour Code
• Efficient Deterministic Preparation of Quantum States Using Decision Diagrams
• Continuous-Time Quantum Walks on Dynamic Graphs
• Multi-Angle QAOA Does Not Always Need All Its Angles
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Performance Analysis of Multi-Angle QAOA for p > 1
• Isolated Vertices in Continuous-Time Quantum Walks on Dynamic Graphs
• Simplifying Continuous-Time Quantum Walks on Dynamic Graphs
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• Quantum approximate optimization algorithm with random and subgraph phase operators
• Implementing Quantum Gates Using Length-3 Dynamic Quantum Walks