Fewer Quantum Measurements Unlock Faster Channel Construction

A new algorithm efficiently learns nearly sparse unitaries, a key step towards simplifying complex quantum processes. Zahra Honjani and Mohsen Heidari at Indiana University have constructed a quantum channel closely approximating an unknown unitary using a number of forward queries scaling as $\tilde{O}(s^6/ε^4)$. The work sharply advances the field by extending sparse recovery techniques to general unitaries and establishing a learning guarantee for a broad class of unitaries with bounded Pauli norms. It also demonstrates limitations through an exponential query lower bound for unrestricted unitaries. Efficiently learned unitaries have implications for optimising quantum circuits and developing more manageable models of quantum systems.

Efficient learning of sparse unitaries via optimised Pauli coefficient estimation

The query complexity for learning nearly sparse unitaries has been reduced to $\tilde{O}(s^6/ε^4)$, a substantial improvement over previous algorithms. These earlier algorithms demanded specific structural assumptions, such as subgroup support, meaning the unitary’s action was constrained to a specific subgroup of the unitary group, or access to time-evolution at small timescales, limiting their general applicability. The parameter ‘s’ represents the sparsity of the unitary, specifically the maximum number of significant components in its Pauli decomposition, while ‘ε’ controls the acceptable error in the approximation. This advance unlocks the potential for optimising quantum circuits and creating more manageable models of complex quantum systems, particularly those with a limited number of dominant components. Understanding and controlling these components is crucial for tasks like quantum error correction and efficient simulation of physical systems.

The new algorithm efficiently constructs a quantum channel approximating an unknown unitary, guaranteeing a close match in diamond distance, a measure of how distinguishable two quantum processes are. The diamond distance quantifies the maximum difference in the output of the two processes over all possible input states, providing a rigorous measure of their similarity. Crucially, the algorithm accurately estimates the important Pauli coefficients defining the unitary’s behaviour. A key step towards more flexible quantum process tomography has been demonstrated: an algorithm capable of estimating all significant Pauli coefficients of an unknown unitary, requiring O(log(1/θ) ε 4 ) queries, where θ represents a desired accuracy threshold. Further analysis revealed that unitaries with a bounded Pauli $\ell_$1-norm, a measure of the total magnitude of the coefficients (sum of absolute values), are learnable under a restricted diamond distance metric with $\tilde{O}(L_1^8/ε^{16})$ queries. This represents a significant improvement over the exponential lower bound of Ω(2 n/2 ) for standard diamond distance learning, where ‘n’ is the dimension of the Hilbert space. The $\ell_$1-norm provides a robust measure of sparsity, as it prioritises identifying the largest coefficients. Nearly $(s,ε)$-sparse unitaries can be learned in diamond distance with a query complexity of $\tilde{O}(s^6/ε^4)$, alongside a polynomial time quantum algorithm achieving the same. However, building practical implementations and demonstrating scalability beyond small systems remains a considerable challenge, requiring significant advancements in quantum hardware and error mitigation techniques. The algorithm leverages techniques from compressed sensing and matrix completion to efficiently estimate the Pauli coefficients from a limited number of measurements.

Defining the boundaries of efficient quantum system characterisation through unitary sparsity

Efficient characterisation of quantum systems is vital for verifying and improving the performance of emerging quantum technologies. This new work offers a significant step forward by streamlining the process of learning unitaries, the fundamental building blocks of quantum computation, and accurately identifying their key components. Unitaries lacking a sparse structure, those not built from a limited number of components, however, present an exponential challenge, requiring exponentially more resources to learn. This is because the number of parameters needed to describe a general unitary scale exponentially with the system size, making it intractable to learn from limited data. The concept of sparsity, therefore, is crucial for making quantum system characterisation feasible.

These findings pinpoint precisely where current methods falter, guiding future work towards algorithms better suited to highly entangled systems, and do not diminish the value of this work. The techniques for efficiently estimating Pauli coefficients, which describe the fundamental building blocks of quantum operations, remain a powerful tool for analysing simpler, more practical quantum circuits. Pauli operators form a basis for all quantum operations, and accurately estimating their coefficients allows for a complete description of the unitary transformation. A new algorithm for efficiently learning nearly sparse unitaries, complex transformations central to quantum computation, has been established by accurately reconstructing their key components. Achieving a query complexity of approximately $\tilde{O}(s^6/ε^4)$, the method surpasses previous limitations requiring specific structural assumptions or restricted operational conditions. The implications extend to areas such as quantum machine learning, where sparse unitaries can be used to construct efficient quantum algorithms, and quantum simulation, where they can simplify the modelling of complex physical systems. Furthermore, this work provides a theoretical foundation for developing more robust and scalable quantum algorithms, and will open new avenues for designing algorithms suited to more intricate, entangled systems. The ability to efficiently learn nearly sparse unitaries is a crucial step towards realising the full potential of quantum computation and information processing, enabling the development of more powerful and versatile quantum technologies.

The researchers developed a new algorithm to efficiently reconstruct nearly sparse unitaries, which are complex transformations used in quantum computation. This method achieves a query complexity of approximately $\tilde{O}(s^6/ε^4)$ and represents an improvement over previous techniques that required more restrictive conditions. The findings demonstrate that these unitaries, characterised by a concentrated Pauli spectrum of at most $s$ components with residual mass of at most $ε$, are learnable using query access. The authors suggest this work will guide future development of algorithms better suited to highly entangled systems.