Measurement Complexity of Quantum Compressed Sensing

Abstract:Conventional compressed sensing (CS) has a measurement lower bound of M = {\Omega}(K log(N/K)) under non-adaptive measurements. Recent experiments on quantum compressed sensing (QCS) have reported numbers of measurements below this classical lower bound. In this work, we establish lower bounds on the measurement complexity of QCS from an information-theoretic and quantum-physical perspective. QCS exploits quantum parallelism, enabling a unitary domain-alignment evolution to act on a superposition of all N basis states and map the sparse basis onto the measurement basis in a one-to-one manner. Consequently, the locations of nonzero components are explicitly carried by measurement-index labels. If only basic statistical information about the K nonzero components is required, the total number of effective index samples satisfies the coarse necessary condition Ms = {\Omega}(K). Under independent single-index projective measurements, when the support is unknown, the nonzero probabilities satisfy pn = {\Theta}(1/K), and exact support recovery is required with a fixed success probability, the sampling-coverage requirement leads to Ms = {\Theta}(K ln K). If each nonzero amplitude coefficient is further required to achieve a coordinate-wise relative root-mean-square error {\epsilon}, the optimal effective index sample complexity is Ms = {\Theta}(K ln K + K/{\epsilon}2), which reduces to {\Theta}(K ln K) for fixed {\epsilon}. Multimode photon-number-resolving detection can reduce the number of experimental rounds but not the total effective index sample complexity. These results show that quantum parallelism is not only a core resource for quantum computing but can also play a transformative role in measurement science.

arXiv:2610.08234 [quant-ph]

(or arXiv:2610.08234v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.08234 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.