Sublinear Classical-to-Quantum Data Encoding using -Toffoli Gates
arXiv:2505.06054 · doi:10.1109/QCE65121.2025.00034
Abstract
Quantum state preparation, also known as encoding or embedding, is a crucial initial step in many quantum algorithms and often constrains theoretical quantum speedup in fields such as quantum machine learning and linear equation solvers. One common strategy is amplitude encoding, which embeds a classical input vector of size N=2\textsuperscript{n} in the amplitudes of an n-qubit register. For arbitrary vectors, the circuit depth typically scales linearly with the input size N, rapidly becoming unfeasible on near-term hardware. We propose a general-purpose procedure with sublinear average depth in N, increasing the window of utility. Our amplitude encoding method encodes arbitrary complex vectors of size N=2\textsuperscript{n} at any desired binary precision using a register with n qubits plus 2 ancillas and a sublinear number of multi-controlled NOT (MCX) gates, at the cost of a probabilistic success rate proportional to the sparsity of the encoded data. The core idea of our procedure is to construct an isomorphism between target states and hypercube graphs, in which specific reflections correspond to MCX gates. This reformulates the state preparation problem in terms of permutations and \emph{binary addition}. The use of MCX gates as fundamental operations makes this approach particularly suitable for quantum platforms such as \emph{ion traps} and \emph{neutral atom devices}. This geometrical perspective paves the way for more gate-efficient algorithms suitable for near-term hardware applications.
References in corpus (28)
- Quantum algorithm for solving linear systems of equations
- Quantum random access memory
- Synthesis of Quantum Logic Circuits
- Quantum Error Mitigation
- Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
- Quantum-state preparation with universal gate decompositions
- Quantum Circuits for Isometries
- A divide-and-conquer algorithm for quantum state preparation
- Quantum circuits with uniformly controlled one-qubit gates
- Circuit-Based Quantum Random Access Memory for Classical Data
- Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicator
- Fault tolerant resource estimation of quantum random-access memories
- Quantum Circuits for Sparse Isometries
- Configurable sublinear circuits for quantum state preparation
- Efficient quantum amplitude encoding of polynomial functions
- Quantum algorithms for approximate function loading
- Double sparse quantum state preparation
- Low-rank quantum state preparation
- Efficient Deterministic Preparation of Quantum States Using Decision Diagrams
- One-step implementation of Toffoli gate for neutral atoms based on unconventional Rydberg pumping
- Approximate encoding of quantum states using shallow circuits
- Quantum algorithm for partial differential equations of non-conservative systems with spatially varying parameters
- Tensor network noise characterization for near-term quantum computers
- Noise-Robust Detection of Quantum Phase Transitions
- Fundamental causal bounds of quantum random access memories
- Prolonging a discrete time crystal by quantum-classical feedback
- High-fidelity quantum state preparation using neighboring optimal control
- T-Count Optimizing Genetic Algorithm for Quantum State Preparation