Source-linked AI summary
Circuit-Based Quantum Random Access Memory for Classical Data
Daniel K. Park, Francesco Petruccione, June-Koo Kevin Rhee
TL;DR
Quantum algorithms need an efficient way to encode classical data into quantum states, while prepared states cannot generally be reused after measurement. The paper presents circuit-based FF-QRAM for constructing and updating quantum databases, requiring O(n) qubits and O(Mn) steps, and introduces quantum forking to reduce QRAM queries in certain applications.
Problem
Quantum information processing requires efficient conversion of classical data into quantum states, while prepared QRAM inputs cannot generally be reused after measurement or copied.
Method
The paper develops circuit-based flip-flop QRAM to construct and update quantum databases, with post-selection enabling continuous data encoding as probability amplitudes.
Results
O(n) qubits and O(Mn) flip-register-flop steps register n-bit classical data with arbitrary probability amplitudes across M memory cells.
Takeaways & Limitations
Quantum forking can reduce QRAM queries in certain applications while enabling independent unitary processes in superposition.
Takeaways & Limitations
Post-selection adds a data-dependent runtime factor of ∼1/P(1), although preprocessing can improve success probability in some instances.
Abstract
from arXiv · showhide
A prerequisite for many quantum information processing tasks to truly surpass classical approaches is an efficient procedure to encode classical data in quantum superposition states. In this work, we present a circuit-based flip-flop quantum random access memory to construct a quantum database of classical information in a systematic and flexible way. For registering or updating classical data consisting of $M$ entries, each represented by $n$ bits, the method requires $O(n)$ qubits and $O(Mn)$ steps. With post-selection at an additional cost, our method can also store continuous data as probability amplitudes. As an example, we present a procedure to convert classical training data for a quantum supervised learning algorithm to a quantum state. Further improvements can be achieved by reducing the number of state preparation queries with the introduction of quantum forking.
Introduction
Efficient classical-to-quantum data encoding is needed for quantum algorithms, but practical schemes must also address implementation assumptions and repeated state preparation. The paper proposes circuit-based FF-QRAM and introduces quantum forking to reduce QRAM queries in certain applications.
- Efficiently generating arbitrary quantum input states is necessary for practical quantum algorithms processing complex classical data.
- The scheme’s practicality depends on inactive routing elements not introducing noticeable errors.
- FF-QRAM uses standard circuit-based computation without a routing algorithm to write, update, and superpose unsorted classical data with non-uniform amplitudes.The construction uses O(n) qubits and O(Mn) quantum operations for M entries represented by n bits.
- Quantum database states generally cannot be reused after measurement or copied, making QRAM preparation costly across algorithms with identical inputs.
- Quantum forking is introduced to split unitary processes in superposition and reduce QRAM queries in certain applications.
Results
The flip-flop QRAM constructs quantum databases from classical data with circuit-based operations, supports amplitude encoding and updates, and extends state preparation through quantum forking. Its main trade-offs are post-selection overhead and potentially dominant register-operation costs.
- Quantum database construction: A QDB represents classical bit strings in computational-basis states, with probability amplitudes encoding continuous data or normalized data occurrence.For M n-bit data entries, n + m qubits are sufficient, where m relates to the address register.
- Flip-flop QRAM: The FF-QRAM uses classically controlled Pauli-X gates and n-qubit controlled rotations to selectively flip, rotate, and restore bus states while registering successive data entries.The process repeats across entries and can assign non-uniform weights; selective flip-flop operations also support updates to existing databases.
- Amplitude encoding and overhead: Post-selection matches rotation angles to desired amplitudes but increases total runtime by a data-dependent factor of ∼1/P(1).Pre-processing can improve the success probability in some distance-based classification instances; post-selection is unnecessary for some binary-data transformations.
- Implementation considerations: Register-operation gates can dominate total QRAM runtime, making efficient implementation of the multi-qubit controlled rotation critical for practicality.The paper notes that circuit-depth reductions depend on the gate set available in a specific experimental setup.
- Application to quantum support vector machine: O(log2(MN)) hardware resources and O(MN) flip-register-flop operations construct the quantum database for the quantum support vector machine.The circuit writes training-data components through rotations determined by elements of the training vector, after post-selecting the register outcome |1⟩R.
- Quantum forking: Quantum forking applies independent unitary processes in superposition, reducing QRAM queries for certain applications and enabling real-part inner-product estimation.With an arbitrary ancilla, the described method uses O(n) additional gates and reduces QRAM queries by a factor of ∼1/2; adding a phase gate accesses the imaginary part.
Discussion
The paper proposes a circuit-based flip-flop QRAM for encoding classical data flexibly, while identifying post-selection, resource overhead, and state reusability as practical considerations.
- Architecture: FF-QRAM registers n-bit classical data with arbitrary probability amplitudes using O(n) qubits and O(Mn) flip-register-flop steps.It supports discrete information as qubits and continuous information as probability amplitudes.
- Architecture: The architecture is implemented with standard quantum circuits, providing compatibility with quantum computing techniques without relying on a routing algorithm.
- Resource considerations: Register-operation overhead can dominate the runtime beyond the O(Mn) flip-register-flop steps.
- Quantum forking: Quantum forking addresses QDB non-reusability after measurement and can reduce QRAM queries in some applications, including inner-product evaluation.Finding further applications with even constant query reductions remains open.
Methods
The circuit implementation decomposes multi-controlled operations into Toffoli gates and ancillas, with merged operations reducing depth and an alternative error model reducing the noise-exposed time steps.
- Multi-controlled gates: CnNOT is recursively decomposed into 2n − 3 Toffoli gates and n − 2 ancilla qubits prepared in |0⟩.Additional Toffoli gates uncompute the ancillas so they become unentangled from the system.
- Circuit depth: The ¯cX operations between consecutive controlled rotations can be merged, reducing circuit depth under the stated simultaneous-operation assumption.
- Gate accounting: Writing M classical data entries of length n uses n(M + 1) single-qubit gates, while each CnRy(θ) uses two single-qubit gates and two CnNOT gates.
- Noise exposure: The CnNOT implementation exposes 2n − 1 qubits to 2⌈log2(n)⌉ − 1 time steps.
- Noise exposure: If each CnRy(θ) requires only n + 1 independent errors, the noise-exposed time becomes (n + 1)M + n(M + 1).