Circuit complexity of quantum access models for encoding classical data
arXiv:2311.11365 · doi:10.1038/s41534-024-00835-8
Abstract
Classical data encoding is usually treated as a black-box in the oracle-based quantum algorithms. On the other hand, their constructions are crucial for practical algorithm implementations. Here, we open the black-boxes of data encoding and study the Clifford complexity of constructing some typical quantum access models. For general matrices, we show that both sparse-access input models and block-encoding require nearly linear circuit complexities relative to the matrix dimension, even if matrices are sparse. We also gives construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is the linear combination polynomial terms of efficient unitaries. As a typical example, we propose improved block encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a selective oracle for Pauli strings, which hold independent value. Our access model constructions offer considerable flexibility, allowing for tunable ancillary qubit number and offers corresponding space-time trade-offs.
21 pages, 1 figure
References in corpus (32)
- Quantum Machine Learning
- 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
- Quantum Convolutional Neural Networks
- Quantum random access memory
- Hamiltonian Simulation by Qubitization
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Toward the first quantum simulation with quantum speedup
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- On the relationship between continuous- and discrete-time quantum walk
- Quantum-state preparation with universal gate decompositions
- The General Quantum Interference Principle and the Duality Computer
- A quantum-inspired classical algorithm for recommendation systems
- Exponential improvement in precision for simulating sparse Hamiltonians
- Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
- Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
- Efficient Scheme for Initializing a Quantum Register with an Arbitrary Superposed State
- Simulating sparse Hamiltonians with star decompositions
- Resilience of quantum random access memory to generic noise
- On the statistical complexity of quantum circuits
- Entangling power and quantum circuit complexity
- Exponential quantum speedup in simulating coupled classical oscillators
- Block-encoding structured matrices for data input in quantum computing
- Quantum Resources Required to Block-Encode a Matrix of Classical Data
- Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
- Quantum state preparation protocol for encoding classical data into the amplitudes of a quantum information processing register's wave function
- Data centers with quantum random access memory and quantum networks
- Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
- Parallel Quantum Algorithm for Hamiltonian Simulation
Cited by in corpus (14)
- Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
- Fault-tolerant quantum algorithms for quantum molecular systems: A survey
- Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
- Exponential quantum advantages for practical non-Hermitian eigenproblems
- Encoding of linear kinetic plasma problems in quantum circuits via data compression
- Reducing Circuit Depth in Quantum State Preparation for Quantum Simulation Using Measurements and Feedforward
- Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
- Adaptive Lattice Gas Algorithm: Classical and Quantum implementations
- Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
- Resource-Dependent Complexity of Quantum Channels
- Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
- Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
- Robust and optimal loading of general classical data into quantum computers