A divide-and-conquer algorithm for quantum state preparation

Abstract

Advantages in several fields of research and industry are expected with the rise of quantum computers. However, the computational cost to load classical data in quantum computers can impose restrictions on possible quantum speedups. Known algorithms to create arbitrary quantum states require quantum circuits with depth O(N) to load an N-dimensional vector. Here, we show that it is possible to load an N-dimensional vector with a quantum circuit with polylogarithmic depth and entangled information in ancillary qubits. Results show that we can efficiently load data in quantum devices using a divide-and-conquer strategy to exchange computational time for space. We demonstrate a proof of concept on a real quantum device and present two applications for quantum machine learning. We expect that this new loading strategy allows the quantum speedup of tasks that require to load a significant volume of information to quantum devices.

References in corpus (4)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Synthesis of Quantum Logic Circuits
• Circuit-Based Quantum Random Access Memory for Classical Data
• Accelerating Data Loading in Deep Neural Network Training

Cited by in corpus (70)

• Quantum convolutional neural network for classical data classification
• Biology and medicine in the landscape of quantum advantages
• Variational quantum algorithm based on the minimum potential energy for solving the Poisson equation
• Classical-to-quantum convolutional neural network transfer learning
• Constant-depth preparation of matrix product states with adaptive quantum circuits
• Configurable sublinear circuits for quantum state preparation
• Quantum algorithms for approximate function loading
• Efficient quantum amplitude encoding of polynomial functions
• Variational Quantum Evolution Equation Solver
• Two quantum algorithms for solving the one-dimensional advection-diffusion equation
• Low-rank quantum state preparation
• Towards Quantum Computational Mechanics
• Variational quantum one-class classifier
• Fast Black-Box Quantum State Preparation
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Automatically Differentiable Quantum Circuit for Many-qubit State Preparation
• Representation of binary classification trees with binary features by quantum circuits
• Quantum Convolutional Neural Networks with Interaction Layers for Classification of Classical Data
• Array Antenna Power Pattern Analysis Through Quantum Computing
• Sparse Quantum State Preparation for Strongly Correlated Systems
• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
• Neural Quantum Embedding: Pushing the Limits of Quantum Supervised Learning
• A Variational Approach to the Quantum Separability Problem
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Variational quantum state discriminator for supervised machine learning
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers
• Boundary Treatment for Variational Quantum Simulations of Partial Differential Equations on Quantum Computers
• Solving The Vehicle Routing Problem via Quantum Support Vector Machines
• Simulating noisy quantum channels via quantum state preparation algorithms
• Efficient Quantum Lattice Gas Automata
• Quantum Text Encoding for Classification Tasks
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
• Quantum support vector data description for anomaly detection
• State preparation of AGP on a quantum computer without number projection
• A novel approach for quantum financial simulation and quantum state preparation
• Quantum data encoding as a distinct abstraction layer in the design of quantum circuits
• Simulation of positive operator-valued measures and quantum instruments via quantum state preparation algorithms
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method
• Quantum Architecture Search for Quantum Monte Carlo Integration via Conditional Parameterized Circuits with Application to Finance
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• Quantum Algorithm for Smoothed Particle Hydrodynamics
• Optimisation-free Classification and Density Estimation with Quantum Circuits
• A Post-Training Approach for Mitigating Overfitting in Quantum Convolutional Neural Networks
• Numerical circuit synthesis and compilation for multi-state preparation
• Quantum encoder for fixed Hamming-weight subspaces
• Efficient Quantum Circuits based on the Quantum Natural Gradient
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• Conditions for a quadratic quantum speedup in nonlinear transforms with applications to energy contract pricing
• Quantum State Preparation Using an Exact CNOT Synthesis Formulation
• Holonomic swap and controlled-swap gates of neutral atoms via selective Rydberg pumping
• Quantum Multiplexer Simplification for State Preparation
• Quadratic Quantum Speedup for Perceptron Training
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Krylov Spread Complexity of Quantum-Walks
• Optimal Qubit Mapping Search for Encoding Classical Data into Matrix Product State Representation with Minimal Loss
• Quadratic speed-ups in quantum kernelized binary classification
• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• Notes on Quantum Computing for Thermal Science
• Sublinear Classical-to-Quantum Data Encoding using $n$-Toffoli Gates
• Quantum State Preparation Of Multiconfigurational States For Quantum Chemistry
• T-Count Optimizing Genetic Algorithm for Quantum State Preparation
• Gravitational-wave matched filtering on a quantum computer
• Classification using a two-qubit quantum chip
• Comparing Algorithms for Loading Classical Datasets into Quantum Memory
• Efficient Simulation of Open Quantum Systems on NISQ Trapped-Ion Hardware
• Schmidt quantum compressor
• Thermality versus objectivity: can they peacefully coexist?
• Quantum Encoding of Structured Data with Matrix Product States
• Tucker iterative quantum state preparation