Source-linked AI summary
A divide-and-conquer algorithm for quantum state preparation
Israel F. Araujo, Daniel K. Park, Francesco Petruccione, Adenilton J. da Silva
TL;DR
Quantum algorithms can be limited by the cost of loading classical data, since known arbitrary-state methods require depth O(N) for an N-dimensional vector. The paper proposes divide-and-conquer state preparation with polylogarithmic depth by exchanging time for space, and reports a real-device proof of concept plus machine-learning applications.
Problem
Classical-data loading can dominate quantum computational costs, while known arbitrary-state preparation requires depth O(N) for an N-dimensional vector.
Method
The paper modifies amplitude encoding with controlled swaps and ancilla qubits, using a divide-and-conquer strategy to prepare amplitudes with entangled ancillary information.
Results
The method loads an N-dimensional real vector with circuit depth O(log2(N)) and space O(N), and was demonstrated as a proof of principle on the IBM quantum cloud platform.
Takeaways & Limitations
The time–space tradeoff may benefit quantum machine learning and other algorithms that must load substantial classical data, especially when wider circuits are easier than deeper ones.
Takeaways & Limitations
The method requires a linear number of qubits and entangles ancillary information with the data register, unlike methods using logarithmically many qubits.
Abstract
from arXiv · showhide
Advantages in several fields of research and industry are expected with the rise of quantum computers. However, the computational cost to load classical data in quantum computers can impose restrictions on possible quantum speedups. Known algorithms to create arbitrary quantum states require quantum circuits with depth O(N) to load an N-dimensional vector. Here, we show that it is possible to load an N-dimensional vector with a quantum circuit with polylogarithmic depth and entangled information in ancillary qubits. Results show that we can efficiently load data in quantum devices using a divide-and-conquer strategy to exchange computational time for space. We demonstrate a proof of concept on a real quantum device and present two applications for quantum machine learning. We expect that this new loading strategy allows the quantum speedup of tasks that require to load a significant volume of information to quantum devices.
1 Introduction
The paper frames quantum data loading as a practical bottleneck and proposes a divide-and-conquer encoding that exchanges circuit depth for qubits and ancilla entanglement.
- Quantum data-loading costs can dominate the asymptotic cost of quantum algorithms and large-scale training workflows.
- Existing arbitrary-state loading circuits require exponential depth in the number of qubits, or polynomial depth in the data size.
- The proposed encoding stores an N-dimensional vector in computational-basis amplitudes while entangling ancillary qubits with the data register.
- The approach trades lower circuit depth for greater circuit width and a mixed data-register state when ancillas are traced out.
- The divide-and-conquer method reduces quantum circuit depth to O(log2(N)) using O(N) qubits.
2 Transformation of quantum states
The standard amplitude-encoding procedure recursively computes rotation angles and applies controlled rotations to load a vector, but its quantum operations are sequential.
- Standard amplitude encoding: The generated circuit uses n = log2(N) qubits and controlled one-qubit rotations to prepare the amplitude-encoded state.
- Standard amplitude encoding: Amplitude encoding recursively reduces subvectors to norms and computes rotation angles for loading a real vector’s amplitudes.
- Circuit construction: For an eight-dimensional vector, the example circuit uses O(N) multi-controlled gates sequentially, giving quantum depth O(N).
- Complexity: The classical angle computation and circuit generation each have O(N) computational cost, while the spatial cost is O(log2(N)).
3 Divide-and-conquer loading data
The proposed loading strategy builds the target state bottom-up by preparing small states, weighting them, and combining them through controlled swaps.
- Bottom-up construction: The algorithm divides the input into two-dimensional subvectors and begins by loading normalized one-qubit states at the leaves.
- Bottom-up construction: Child states are weighted by their parent values to form larger left and right states in successive levels of the state-tree.
- State combination: Combining the left and right states with their parent weights generates the desired quantum state.
- Controlled-swap combination: A circuit using m−1 controlled-swap operations combines two (m−1)-qubit states with a one-qubit control state.
- Controlled-swap combination: The resulting construction places the desired output in the first m qubits while storing unit entangled information in m−1 ancillary qubits.
3.1 Loading Complex data
The divide-and-conquer strategy extends state preparation to complex vectors by adding phase rotations to amplitude loading. Controlled-swap operations combine recursively prepared states in parallel, achieving depth O(log^2(N)) with entangled ancillary qubits.
- Complex-vector encoding: The strategy loads complex vector amplitudes |x_k|e^{iω_k} by combining amplitude preparation with Rz phase rotations.The Rz rotations follow the Ry rotations and encode the phases of the input vector.
- Ancillary resources: Preparing the complex state requires N qubits with entangled auxiliary qubits, while the circuit modification adds Rz(λj,v) rotations.The ancillary qubits support the controlled-swap combination of child states.
- Circuit construction: Algorithm 3 initializes qubits with Ry(α_k), applies Rz rotations for phases, and combines states through controlled-swap operations.The angle-tree organizes qubits and angles so gates at the same layer can be drawn in parallel.
- Parallel combination: States in the same state-tree layer are prepared in parallel because their controlled-swap gates use different qubits.Controls occupy one angle-tree layer, while targets lie in corresponding subtrees.
- Depth: The resulting circuit has depth O(log^2(N)), as stated by Theorem 1.The depth accumulates across tree layers as O(1+2+···+log^2(N)−1).
3.2 Orthonormal ancillary
The ancillary states can be made orthonormal by adding a label register and copying data-qubit labels into it with controlled-NOT gates.
- Orthonormalization: The ancillary states are not necessarily orthogonal, so the method adds label qubits to ensure orthonormality.The label register contains log2(N) qubits.
- Label register: The label register starts in |0⟩^⊗log2(N), and log2(N) controlled-NOT gates are applied, each controlled by a data qubit.The resulting labeled ancillary states are written as |ψ_k⟩|k⟩.
- Result: The labeled ancillary states {|ψ̃_k⟩} are orthonormal.The construction appends distinct computational-basis labels to the ancillary states.
3.3 Experiments
Experiments demonstrate the method on a simulator and IBM’s ibmq rome device, then compare circuit depth against prior state-preparation algorithms. The strategy trades lower depth for greater width and entangled ancillary information, with small-vector overhead and linear qubit usage as boundaries.
- Experimental design: The evaluation uses a simulator, a NISQ computer for proof of concept, and random-input comparisons of circuit depth against prior algorithms.The experiments assess both practical execution and depth scaling.
- NISQ demonstration: The proof-of-concept experiment loads four-dimensional data into a two-qubit state on IBM’s five-qubit ibmq rome device.The small dimension was chosen for compatibility with currently available quantum devices.
- NISQ demonstration: The Rome device produced output very close to the expected result after 1024 executions.The implemented circuit contained 10 CNOT operators because limited qubit connectivity required a quantum swap.
- Circuit depth: The proposed method exchanges circuit depth for circuit width compared with previous approaches.This trade-off is the central comparison reported for the divide-and-conquer strategy.
- Circuit depth: The method uses a linear number of qubits rather than the logarithmic number used by other methods, while entangling information in ancillary qubits.These are identified as the method’s two main disadvantages.
- Circuit depth: Higher depth for small vectors results from using three-qubit gates to combine vectors.The paper suggests dividing into larger power-of-two blocks and combining sequentially prepared blocks to improve performance.
3.4 Example Applications
The paper evaluates divide-and-conquer encoding in TTN classifiers against amplitude and qubit encoding, finding comparable classification accuracy while reducing encoding depth relative to amplitude encoding for N ≥64. It also applies the encoding with a swap test to calculate statistical quantities and obtain a covariance-matrix speedup for multivariate variables.
- Hierarchical Quantum Classifier: The TTN classifier applies two-qubit unitaries hierarchically, discarding one output per pair until one measured qubit remains.The circuit uses repeated layers and measurements to approximate the final qubit’s expectation value.
- Hierarchical Quantum Classifier: Similar classification accuracy was obtained for all encodings, with qubit encoding favored because it provides more optimization parameters.The comparison used Iris, Haberman’s Survival, Banknote Authentication, and Pima Indians Diabetes datasets, with ten random initializations.
- Hierarchical Quantum Classifier: The divide-and-conquer encoding represents data using log2(N) qubits instead of the initial state’s N −1 qubits, producing a lower-depth classifier than qubit encoding.This advantage concerns the reduced number of qubits in the encoded data representation.
- Hierarchical Quantum Classifier: The encoding circuit has lower depth than amplitude encoding for N ≥64, while amplitude and divide-and-conquer classification performances are statistically equivalent across all datasets.The equivalence was tested with a Wilcoxon paired signed-rank test at α = 0.05.
- Swap Test: The divide-and-conquer state preparation supports a modified swap test whose σz expectation value yields quantities such as E(X), E(Y), and E(XY).The construction uses orthonormal ancillary states and controlled-swap operations between test and data registers.
- Swap Test: For covariance matrices of two variables with m discrete random variables of size N, the classical cost is Oc(Nm2), whereas the quantum approach uses Oc(N)+Oq(log2(N)).The quantum algorithm retains Oq(log2(N)) total time complexity because the swap test adds only O(log2(N)) controlled-swap gates.
4 Discussion
The discussion presents the method as a quantum data-loading strategy that reduces circuit depth by increasing space and entanglement, while identifying practical trade-offs and open questions. It reports proof-of-principle validation on IBM hardware and applications to quantum machine learning and statistical analysis.
- An efficient classical-data encoding method addresses the open problem of loading data into quantum states for practical quantum computing.
- O(log2(N)) circuit depth and O(N) space provide an exponential time speedup for loading an N-dimensional real vector.
- The speedup uses ancilla qubits entangled with data-register qubits, creating a time–space trade-off.
- Proof-of-principle experiments on an IBM quantum cloud platform verified the method’s validity and feasibility.
- The authors identify efficient ancilla uncomputation and broader divide-and-conquer applications as open directions.
5 Methods
The methods section describes a five-qubit IBM hardware experiment, circuit transpilation for its physical layout, and software-based circuit-depth and hybrid-classification evaluations.
- The proof-of-concept used ibmq rome, a publicly available IBM device with five superconducting qubits.
- The Fig. 5b circuit was compiled to ibmq rome’s physical qubit layout and executed 1024 times to generate Fig. 5a data.
- Figure 7 shows the transpiled circuit, with U1, U2, and U3 denoting IBM physical single-qubit gates with one, two, and three parameters.
- State-preparation circuit depths were computed with Python implementations of Algorithm 3, the cited qiskit method, and a non-optimized baseline.
- Hybrid-classification simulations used Pennylane’s default-qubit state simulator with separate training, validation, and test datasets.
- Training stopped after 30 consecutive validation tests without improvement or after 200 iterations.