Black-box quantum state preparation without arithmetic

Abstract

Black-box quantum state preparation is an important subroutine in many quantum algorithms. The standard approach requires the quantum computer to do arithmetic, which is a key contributor to the complexity. Here we present a new algorithm that avoids arithmetic. We thereby reduce the number of gates by a factor of 286-374 over the best prior work for realistic precision; the improvement factor increases with the precision. As quantum state preparation is a crucial subroutine in many approaches to simulating physics on a quantum computer, our new method brings useful quantum simulation closer to reality.

arXiv commentThis version is identical in content to the published version. Presentation much improved and Table I added

References in corpus (15)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Data Fitting
• On the relationship between continuous- and discrete-time quantum walk
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Preconditioned quantum linear system algorithm
• Halving the cost of quantum addition
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Optimizing Quantum Circuits for Arithmetic
• Black-box Hamiltonian simulation and unitary implementation

Cited by in corpus (68)

• Quantum computational chemistry
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Quantum computing for finance
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicator
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• Exponential quantum speedup in simulating coupled classical oscillators
• A Co-Design Framework of Neural Networks and Quantum Circuits Towards Quantum Advantage
• Configurable sublinear circuits for quantum state preparation
• Efficient quantum amplitude encoding of polynomial functions
• Quantum algorithms for approximate function loading
• Quantum State Preparation of Normal Distributions using Matrix Product States
• Double sparse quantum state preparation
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Grover search revisited; application to image pattern matching
• Quantum state preparation protocol for encoding classical data into the amplitudes of a quantum information processing register's wave function
• Cost function embedding and dataset encoding for machine learning with parameterized quantum circuits
• Fast Black-Box Quantum State Preparation
• Efficient Deterministic Preparation of Quantum States Using Decision Diagrams
• Automatically Differentiable Quantum Circuit for Many-qubit State Preparation
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Representation of binary classification trees with binary features by quantum circuits
• Approximate complex amplitude encoding algorithm and its application to data classification problems
• Quantum algorithms for scientific computing
• Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory
• Quantum Simulation of Realistic Materials in First Quantization Using Non-local Pseudopotentials
• Optimal Hamiltonian simulation for time-periodic systems
• Accelerating Quantum Relaxation via Temporary Reset: A Mpemba-Inspired Approach
• A Quantum Interior-Point Predictor-Corrector Algorithm for Linear Programming
• Automatic quantum circuit encoding of a given arbitrary quantum state
• Fast Black-Box Quantum State Preparation Based on Linear Combination of Unitaries
• Quantum state preparation for multivariate functions
• Implementing smooth functions of a Hermitian matrix on a quantum computer
• A novel approach for quantum financial simulation and quantum state preparation
• Black-Box Quantum State Preparation with Inverse Coefficients
• Quantum data encoding as a distinct abstraction layer in the design of quantum circuits
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Towards AutoQML: A Cloud-Based Automated Circuit Architecture Search Framework
• Noise-Aware Quantum Amplitude Estimation
• Quantum mean estimation for lattice field theory
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• Quantum Algorithm for Vibronic Dynamics: Case Study on Singlet Fission Solar Cell Design
• QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
• Calculating response functions of coupled oscillators using quantum phase estimation
• Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
• Quantum and Classical Algorithms for Approximate Submodular Function Minimization
• Preparing Many Copies of a Quantum State in the Black-Box Model
• Improved quantum algorithm for calculating eigenvalues of differential operators and its application to estimating the decay rate of the perturbation distribution tail in stochastic inflation
• Quantum eigenvalue processing
• Conditional Generative Models for Learning Stochastic Processes
• Quantum state preparation via piecewise QSVT
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
• Quantum Amplitude Arithmetic
• A general approach to quantum integration of cross sections in high-energy physics
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation
• Towards a Pattern Language for Quantum Algorithms
• Quantum algorithm for copula-based risk aggregation using orthogonal series density estimation
• Quantum algorithm for solving McKean-Vlasov stochastic differential equations
• Time series generation for option pricing on quantum computers using tensor network
• Quantum Encoding of Structured Data with Matrix Product States
• A simple quantum simulation algorithm with near-optimal precision scaling