Sublinear Classical-to-Quantum Data Encoding using $n$-Toffoli Gates

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 (9)

• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Synthesis of Quantum Logic Circuits
• Quantum-state preparation with universal gate decompositions
• Circuit-Based Quantum Random Access Memory for Classical Data
• One-step implementation of Toffoli gate for neutral atoms based on unconventional Rydberg pumping
• Quantum algorithm for partial differential equations of non-conservative systems with spatially varying parameters
• High-fidelity quantum state preparation using neighboring optimal control
• T-Count Optimizing Genetic Algorithm for Quantum State Preparation

Cited by in corpus (1)

• Fast Quantum Amplitude Encoding of Typical Classical Data