Quantum memory gets a boost from encoding data more efficiently

Danial Motlagh of has developed a new method for quantum read only memory (QROM) that halves its computational cost. The work introduces a dense encoding construction of QROM, where two bits of classical information are stored in each dirty qubit by using both the Z and X bases. On its own, dense encoding provides a 2× improvement over SelectSwap by reducing the leading Toffoli count to N/λ.

Dense Encoding Reduces QROM Toffoli Count to N/λ

This reduction stems from a technique where each dirty qubit temporarily stores two bits of classical information, a departure from previous methods that used only one bit per qubit. Researchers accomplish this by using both the Z and X bases within each qubit, maximizing data density. The core of this improvement lies in the ability to load the QROM table in blocks of 2λ entries, using the same bλ dirty qubits previously required for λ entries.

The work demonstrates that dense encoding, when combined with sequential bit packets, a technique that further optimizes table access, results in a total leading cost of 1/2(1 + 1/b)N/λ. This combined approach provides an approximate fourfold improvement over SelectSwap for large output widths and practical values of ‘b’.

The researchers verified the circuit’s functionality and qubit restoration through a detailed analysis, establishing a Toffoli count bound of ${\tau }_{dense}(1,\lambda )$ ≤ N/λ + (4b + 2)λ-6, with a dirty qubit requirement of $D_{dense}$ = bλ. “Dense encoding uses the two Pauli components of each dirty qubit to load bits from two table entries,” the paper states, outlining the fundamental principle behind the efficiency gain.

QROM Applications in Fault-Tolerant Quantum Algorithms

The efficiency of quantum read-only memory (QROM) has received a boost through a new construction that reduces its computational demands, a development particularly relevant in qubit-constrained quantum systems. This increased data density directly translates to a reduction in the number of operations needed to access the stored information.

Danial Motlagh of Xanadu, the author of the work, focused on the practical limitations of workspace size, where restricting the table-block size and table loading dominate the overall cost. Combining dense encoding with sequential bit packets gives 1/2(1 + 1/b)N/λ, further halving the sequential construction’s leading cost and providing an approximately 4× improvement over SelectSwap in the large-N limit for practical values of b. The research provides a pathway to more efficient quantum algorithms by minimizing the non-Clifford cost associated with QROM, an important component in applications ranging from Hamiltonian simulation to solving differential equations.

SelectSwap and Sequential Packets: Baseline QROM Methods

The ability to load table entries in blocks of 2λ, rather than λ, is central to this efficiency gain. The research demonstrates that the improvements from sequential packets and dense encoding are independent, allowing for synergistic gains in QROM performance.

Analysis detailed in the work shows that the optimized count for the dense encoding construction, when combined with sequential bit packets, consistently outperforms SelectSwap across a range of tested packet widths and block sizes. A diagram illustrating the dense encoding process reveals how a single dirty qubit carries the Pauli choices for two table values, enabling the read operation to apply Z for p = 0 and X for p = 1, controlled by the output qubit.

Combining Dense Encoding with Sequential Bit Packets for 4x Improvement

This approach effectively doubles the data density within the available qubits, impacting the overall efficiency of the QROM process. The researchers detail how dividing the output into packets allows for efficient loading and reading of data, minimizing the number of necessary operations.

The architecture of this optimized QROM relies on a series of controlled reads and restorations of the dirty qubits, ensuring the integrity of the stored information throughout the process. The work’s findings suggest that future research should focus on integrating these logical savings with considerations for Clifford scheduling, measurement latency and physical layout to determine how these improvements translate into practical fault-tolerant implementations.

More like this

Quantum Research NewsA 20-meter fiber keeps photons entangled for complex operations

Quantum Research NewsCat-like quantum states confirmed in a three-photon chip

Quantum PhysicsSparse Hamiltonians can be learned with slower quantum controls

Quantum AlgorithmsSAXON Q’s three qubits hit a 77% target rate at room temperature