Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits

Abstract

As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of $|i⟩|0^n⟩\to |i⟩|{\psi }_i⟩$ for all $i\in \{0,1{\}}^k$ for the given $n$-qubit states $|{\psi }_i⟩$. In this paper, we construct a quantum circuit for implementing CQSP, with depth $O\left(n+k+\frac{2^{n+k}}{n+k+m}\right)$ and size $O\left(2^{n+k}\right)$ for any given number $m$ of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are \optimal for any integer parameters $m,k\ge 0$ and $n\ge 1$. When $k=0$, the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation $|0^n⟩|0^m⟩\to |\psi ⟩|0^m⟩$. This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to $\Theta (n+2^n/(n+m))$ and its size complexity to $\Theta (2^n)$ for any $m$. Another fundamental problem, unitary synthesis, asks to implement a general $n$-qubit unitary by a quantum circuit. Previous work shows a lower bound of $\Omega (n+4^n/(n+m))$ and an upper bound of $O(n{2}^n)$ for $m=\Omega (2^n/n)$ ancillary qubits. In this paper, we quadratically shrink this gap by presenting a quantum circuit of the depth of $O\left(n{2}^{n/2}+\frac{n^{1/2}{2}^{3n/2}}{m^{1/2}}\right)$.

References in corpus (24)

• Quantum Machine Learning
• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Quantum-state preparation with universal gate decompositions
• Architectures for a quantum random access memory
• Minimal Universal Two-qubit Quantum Circuits
• Search via Quantum Walk
• Efficient decomposition of quantum gates
• A quantum linear system algorithm for dense matrices
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Quantum circuits with uniformly controlled one-qubit gates
• Circuit-Based Quantum Random Access Memory for Classical Data
• Quantum singular value decomposition of non-sparse low-rank matrices
• q-means: A quantum algorithm for unsupervised machine learning
• Fault tolerant resource estimation of quantum random-access memories
• Quantum Spectral Clustering
• Circuit-based quantum random access memory for classical data with continuous amplitudes

Cited by in corpus (19)

• Circuit complexity of quantum access models for encoding classical data
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Error Suppression for Arbitrary-Size Black Box Quantum Operations
• Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
• A novel approach for quantum financial simulation and quantum state preparation
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• QRAM: A Survey and Critique
• Numerical circuit synthesis and compilation for multi-state preparation
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Quantum data generation in a denoising model with multiscale entanglement renormalization network
• General Approach to Error Detection of Bosonic Codes via Phase Estimation
• Quantum states supported by matroids
• Quantum algorithm for anisotropic diffusion and convection equations with vector norm scaling
• Robust and optimal loading of general classical data into quantum computers