For many practical applications of quantum computing, the most costly steps involve coherently accessing classical data. We help address this challenge by applying mass production techniques, which can reduce the cost of applying an operation multiple times in parallel. We combine these techniques with modern approaches for classical data loading based on "quantum read-only memory" (QROM). We find that we can polynomially reduce the total number of gates required for data loading, but we find no advantage in cost models that only count the number of non-Clifford gates. Furthermore, for realistic cost models and problem sizes, we find that it is possible to reduce the cost of parallel data loading by an order of magnitude or more. We present several applications of quantum mass production, including a scheme that uses parallel phase estimation to asymptotically reduce the gate complexity of state-of-the-art algorithms for estimating eigenvalues of the quantum chemical Hamiltonian, including both Clifford and non-Clifford gates, from $\widetilde{\mathcal{O}}\left(N_{orb}^2\right)$ to $\widetilde{\mathcal{O}}\left(N_{orb}^{\log_2 3}\right)$, where $N_{orb}$ denotes the number of orbitals. We also show that mass production can be used to reduce the cost of serial calls to the same data loading oracle by precomputing several copies of a novel QROM resource state.
For many practical applications of quantum computing, the most costly steps involve coherently accessing classical data. We help address this challenge by applying mass production techniques, which can reduce the cost of applying an operation multiple times in parallel. We combine these techniques with modern approaches for classical data loading based on "quantum read-only memory" (QROM). We find that we can polynomially reduce the total number of gates required for data loading, but we find no advantage in cost models that only count the number of non-Clifford gates. Furthermore, for realistic cost models and problem sizes, we find that it is possible to reduce the cost of parallel data loading by an order of magnitude or more. We present several applications of quantum mass production, including a scheme that uses parallel phase estimation to asymptotically reduce the gate complexity of state-of-the-art algorithms for estimating eigenvalues of the quantum chemical Hamiltonian, including both Clifford and non-Clifford gates, from O(Norb2) to O(Norblog23), where Norb denotes the number of orbitals. We also show that mass production can be used to reduce the cost of serial calls to the same data loading oracle by precomputing several copies of a novel QROM resource state.
Table lookup, often referred to as quantum read only memory (QROM), is one of the most widely used subroutines in quantum algorithms, and constitutes the majority share of algorithmic overheads in most practical applications of quantum computers. It involves the coherent loading of N bitstrings of length b in superposition, and naively has a non-Clifford cost of N Toffolis. It is known that given access to bλ dirty qubits, one can reduce the Toffoli cost of QROM to 2λN+4b(λ−1). In this work, we first present an optimization to reduce this cost to 2λN+2b(λ−1)+2λ−6 by replacing the ``SelectSwap" architecture with ``SelectCopy". We then provide a further optimization for the qubit-constrained regime where the Toffoli cost is typically ∼2λN, and reduce it to ∼(1+b1)λN, cutting the cost by approximately 50% and effectively matching the performance of clean-qubit QROM using dirty qubits for practical values of b. Lastly, we provide a parametric family of methods that allow the interpolation of the prefactor of the $\frac{N}λ $ term from 2 to (1+b1) to obtain the best cost for different qubit availability regimes.
Quantum read only memory (QROM) is a substantial source of non-Clifford cost in fault-tolerant quantum algorithms. Borrowing dirty qubits can reduce this cost, provided their unknown initial states are restored. We consider the practically relevant qubit-constrained regime, where limited workspace restricts the table-block size and table loading dominates the cost. For N entries of b bits and approximately bλ dirty qubits, SelectSwap has leading Toffoli count 2N/λ. Recent work using sequential bit packets reduces this to (1+1/b)N/λ. In this work we introduce a dense encoding construction of QROM, where two bits of classical information are stored in each dirty qubit instead of one by utilizing 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/λ. Combining it with sequential bit packets gives 21(1+1/b)N/λ, a further halving of the sequential construction's leading cost, and an approximately 4× improvement over SelectSwap in the large-N limit for practical values of b.
Quantum computing is a rapidly expanding field with applications ranging from optimization all the way to complex machine learning tasks. Quantum memories, while lacking in practical quantum computers, have the potential to bring quantum advantage. In quantum machine learning applications for example, a quantum memory can simplify the data loading process and potentially accelerate the learning task. Quantum memory can also store intermediate quantum state of qubits that can be reused for computation. However, the depth, gate count and compilation time of quantum memories such as, Quantum Read Only Memory (QROM) scale exponentially with the number of address lines making them impractical in state-of-the-art Noisy Intermediate-Scale Quantum (NISQ) computers beyond 4-bit addresses. In this paper, we propose techniques such as, pre-decoding logic and qubit reset to reduce the depth and gate count of QROM circuits to target wider address ranges such as, 8-bits. The proposed approach reduces the number of gates and depth count by at least 2X compared to the naive implementation at only 36% qubit overhead. A reduction in circuit depth and gate count as high as 75X and compilation time by 85X at the cost of a maximum of 2.28X qubit overhead is observed. Experimentally, the fidelity with the proposed pre-decoding circuit compared to existing optimization approach is also higher (as much as 73% compared to 40.8%) under reduced error rates.
Efficient encoding of classical data into quantum circuits is a critical challenge that directly impacts the scalability of quantum algorithms. In this work, we present an automated compilation framework for resource-aware quantum data loading tailored to a given input vector and target error tolerance. By explicitly exploiting the trade-off between exact and approximate state preparation, our approach systematically partitions the total error budget between precision and approximation errors, thereby minimizing quantum resource costs. The framework supports a comprehensive suite of state-of-the-art methods, including multiplexer-based loaders, quantum read-only memory (QROM) constructions, sparse encodings, matrix product states (MPS), Fourier series loaders (FSL), and Walsh transform-based diagonal operators. We demonstrate the effectiveness of our framework across several applications, where it consistently uncovers non-obvious, resource-efficient strategies enabled by controlled approximation. In particular, we analyze a computational fluid dynamics workflow where the automated selection of MPS state preparation and Walsh transform-based encoding, combined with a novel Walsh-based measurement technique, leads to resource reductions of over four orders of magnitude compared to previous approaches. We also introduce two independent advances developed through the framework: a more efficient circuit for d-diagonal matrices, and an optimized block encoding for kinetic energy operators. Our results underscore the indispensable role of automated, approximation-aware compilation in making large-scale quantum algorithms feasible on resource-constrained hardware.
Emerging quantum algorithms that process data require that classical input data be represented as a quantum state. These data-processing algorithms often follow the gate model of quantum computing-which requires qubits to be initialized to a basis state, typically| 0 〉-and thus often employ state generation circuits to transform the initialized basis state to a data-representation state. There are many ways to encode classical data in a qubit, and the oft-applied approach of basis encoding does not allow optimization to the extent that other variants do. In this work, we thus consider automatic synthesis of addressable, quantum read-only memory (QROM) circuits, which act as data-encoding state-generation circuits. We investi-gate three data encoding approaches, one of which we introduce to provide improved dynamic range and precision. We present experimental results that compare these encoding methods for QROM synthesis to better understand the implications of and applications for each.
Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the T count of sparse QROM, in which only s of the 2n addresses store nonzero data. We prove that the optimal T count is Θ(n+min{s,s(m+log(2n+1/s))}). Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+T circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching T-count bounds Θ(min{s,slog(2n+1/s)}+slog(1/ε)+log(1/ε)) for s-sparse state preparation and Θ(2ns(n+log(1/εBE))+log(1/εBE)) for block encoding of s-sparse matrices, where ε and εBE are the precision of state preparation and block encoding, respectively.