Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.
Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.
Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.
Encoding classical data into quantum systems is a foundational step in the execution of nearly all quantum algorithms, and a critical bottleneck in realizing practical quantum advantage. This review provides a comprehensive account of the concepts, algorithms, and practical considerations associated with quantum data encoding. We trace the development from its early conceptual foundations to recent advances, considering commonly used access models, such as quantum state preparation, unitary synthesis, QRAM and block encoding. We survey the circuit size, depth, space-time tradeoffs, as well as non-Clifford resources required for fault-tolerant implementation. We also discuss the roles of different access models in quantum algorithms. Special attention is given to structured data, such as sparse data, Boolean functions and data represented by tensor networks. This review bridges theory and applications, serving both as a pedagogical guide for newcomers and as a reference for active researchers. We also highlight the pivotal role of quantum data encoding in quantum computing and provide insights into future directions that will enable quantum advantage.
Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension- N pure quantum state specified by a list of N classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses O ( log ( N / ϵ ) ) clean qubits and a tunable number of ∼ ( λ log ( log N ϵ ) ) dirty qubits, to reduce the T-gate cost to O ( N λ + λ log N ϵ log log N ϵ ) . This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.
Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only k=poly(n) Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in n. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least 1−δ, for any δ. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in n, k, and log(1/δ). These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.
Quantum access to arbitrary classical data encoded in unitary black-box oracles underlies interesting data-intensive quantum algorithms, such as machine learning or electronic structure simulation. The feasibility of these applications depends crucially on gate-efficient implementations of these oracles, which are commonly some reversible versions of the boolean circuit for a classical lookup table. We present a general parametrized architecture for quantum circuits implementing a lookup table that encompasses all prior work in realizing a continuum of optimal trade-offs between qubits, non-Clifford gates, and error resilience, up to logarithmic factors. Our architecture assumes only local 2D connectivity, yet recovers results, with the appropriate parameters, polylogarithmic error scaling. We also identify regimes, such as simultaneous sublinear scaling, in all parameters. These results enable tailoring implementations of the commonly used lookup table primitive to any given quantum device with constrained resources.
Along with the development of quantum technology, finding useful applications of quantum computers has been a central pursuit. Despite various quantum algorithms have been developed, many of them often require strong input assumptions, which is hardware demanding. In particular, recent advances on dequantization have revealed that the quantum advantage is more of a mere artifact of strong input assumptions. In this work, we propose a variant of these algorithms, leveraging both classical and quantum resources. Provided the classical knowledge (the entries) of the matrix/vector of interest, a classical procedure is used to pre-process this information. Then they are fed into a quantum circuit which is shown to be a block encoding of the matrix of interest. From this block-encoding, we show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, preparing ground state, and data fitting. We also analyze our protocol, showing that both the classical and quantum procedure can achieve logarithmic complexity in the input dimension, thus implying its potential for near term realization. We then discuss several implications and corollaries of our result. First,, our results suggest there are certain matrices/Hamiltonians where our method can provide exponential improvement compared to the existing ones with respect to the sparsity. Regarding dense linear systems, our method achieves exponential speed-up with respect to the inverse of error tolerance, compared to the best previously known quantum algorithm for dense systems. Last, and most importantly, regarding quantum data fitting, we show how the output of our quantum algorithms can be leveraged to predict unseen data. Thus, it provides an end-to-end application, which has been an open aspect of the previous quantum data fitting algorithm.