Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0005111 · Physics Letters A

Orthogonality relations in quantum tomography

G.M. D'Ariano, Lorenzo Maccone, M.G.A. Paris

Published Oct 1, 2000• 29 citations
arXivHTMLPDF
DOI
10.1016/s0375-9601(00)00660-5

Related papers

Generalized Orthogonality Relations and SU(1,1)-Quantum Tomography

Claudio Carmeli, Gianni Cassinelli, F. Zizzi

Foundations of Physics•Mar 3, 2009•2 citations

Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit

Armando Bellante, Stefano Vanerio, Stefano Zanero

We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given coherent quantum access to a state and a dictionary of vectors, the goal is to reconstruct the state up to $\ell_2$ error using as few vectors as possible. We first show that the general recovery problem is NP-hard, ruling out efficient exact algorithms in full generality. To overcome this, we introduce Quantum Orthogonal Matching Pursuit (QOMP), the first quantum analogue of the classical OMP greedy algorithm. QOMP combines quantum subroutines for inner product estimation, maximum finding, and block-encoded projections with an error-resetting design that avoids iteration-to-iteration error accumulation. Under standard mutual incoherence and well-conditioned sparsity assumptions, QOMP provably recovers the exact support of a $K$-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in $\ell_2$ norm, achieving query complexity $\widetilde{O}(\sqrt{N}/ε)$ in favorable regimes and reducing tomography to estimating only $K$ coefficients instead of $N$ amplitudes. In particular, for pure-state tomography with $m=O(N)$ dictionary vectors and sparsity $K=\widetilde{O}(1)$ on a well-conditioned subdictionary, this circumvents the $\widetildeΩ(N/ε)$ lower bound that holds in the dense, orthonormal-dictionary setting, without contradiction, by leveraging sparsity together with non-orthogonality. Beyond tomography, we analyze QOMP in the QRAM model, where it yields polynomial speedups over classical OMP implementations, and provide a quantum algorithm to estimate the mutual incoherence of a dictionary of $m$ vectors in $O(m/ε)$ queries, improving over both deterministic and quantum-inspired classical methods.

arXiv:2510.06925•Oct 8, 2025•3 citations

Methods for self-consistent quantum tomography

Cyril Stark

•Jan 1, 2013•1 citation

Preprint arXiv:2510.06925 Submitted on 8 Oct 2025

Armando Bellante, Stefano Vanerio, S. Zanero

We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given coherent quantum access to a state and a dictionary of vectors, the goal is to reconstruct the state up to $\ell_2$ error using as few vectors as possible. We first show that the general recovery problem is NP-hard, ruling out efficient exact algorithms in full generality. To overcome this, we introduce Quantum Orthogonal Matching Pursuit (QOMP), the first quantum analogue of the classical OMP greedy algorithm. QOMP combines quantum subroutines for inner product estimation, maximum finding, and block-encoded projections with an error-resetting design that avoids iteration-to-iteration error accumulation. Under standard mutual incoherence and well-conditioned sparsity assumptions, QOMP provably recovers the exact support of a $K$-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in $\ell_2$ norm, achieving query complexity $\widetilde{O}(\sqrt{N}/ε)$ in favorable regimes and reducing tomography to estimating only $K$ coefficients instead of $N$ amplitudes. In particular, for pure-state tomography with $m=O(N)$ dictionary vectors and sparsity $K=\widetilde{O}(1)$ on a well-conditioned subdictionary, this circumvents the $\widetildeΩ(N/ε)$ lower bound that holds in the dense, orthonormal-dictionary setting, without contradiction, by leveraging sparsity together with non-orthogonality. Beyond tomography, we analyze QOMP in the QRAM model, where it yields polynomial speedups over classical OMP implementations, and provide a quantum algorithm to estimate the mutual incoherence of a dictionary of $m$ vectors in $O(m/ε)$ queries, improving over both deterministic and quantum-inspired classical methods.

•Oct 9, 2025•0 citations

2 Quantum Tomographic Methods

Giacomo Mauro D’Ariano, Matteo G. A. Paris, Massimiliano Federico Sacchi

Lecture notes in physics•Aug 18, 2004•29 citations

On the tomographic picture of quantum mechanics

Alberto Ibort, Vladimir I. Man’ko, Giuseppe Marmo +2 more

arXiv:1004.0102•Physics Letters A•Apr 23, 2010•26 citations
We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given coherent quantum access to a state and a dictionary of vectors, the goal is to reconstruct the state up to ℓ2\ell_2ℓ2​ error using as few vectors as possible. We first show that the general recovery problem is NP-hard, ruling out efficient exact algorithms in full generality. To overcome this, we introduce Quantum Orthogonal Matching Pursuit (QOMP), the first quantum analogue of the classical OMP greedy algorithm. QOMP combines quantum subroutines for inner product estimation, maximum finding, and block-encoded projections with an error-resetting design that avoids iteration-to-iteration error accumulation. Under standard mutual incoherence and well-conditioned sparsity assumptions, QOMP provably recovers the exact support of a KKK-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in ℓ2\ell_2ℓ2​ norm, achieving query complexity O~(N/ε)\widetilde{O}(\sqrt{N}/ε)O(N​/ε) in favorable regimes and reducing tomography to estimating only KKK coefficients instead of NNN amplitudes. In particular, for pure-state tomography with m=O(N)m=O(N)m=O(N) dictionary vectors and sparsity K=O~(1)K=\widetilde{O}(1)K=O(1) on a well-conditioned subdictionary, this circumvents the Ω~(N/ε)\widetildeΩ(N/ε)Ω(N/ε) lower bound that holds in the dense, orthonormal-dictionary setting, without contradiction, by leveraging sparsity together with non-orthogonality. Beyond tomography, we analyze QOMP in the QRAM model, where it yields polynomial speedups over classical OMP implementations, and provide a quantum algorithm to estimate the mutual incoherence of a dictionary of mmm vectors in O(m/ε)O(m/ε)O(m/ε) queries, improving over both deterministic and quantum-inspired classical methods.
We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given coherent quantum access to a state and a dictionary of vectors, the goal is to reconstruct the state up to ℓ2\ell_2ℓ2​ error using as few vectors as possible. We first show that the general recovery problem is NP-hard, ruling out efficient exact algorithms in full generality. To overcome this, we introduce Quantum Orthogonal Matching Pursuit (QOMP), the first quantum analogue of the classical OMP greedy algorithm. QOMP combines quantum subroutines for inner product estimation, maximum finding, and block-encoded projections with an error-resetting design that avoids iteration-to-iteration error accumulation. Under standard mutual incoherence and well-conditioned sparsity assumptions, QOMP provably recovers the exact support of a KKK-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in ℓ2\ell_2ℓ2​ norm, achieving query complexity O~(N/ε)\widetilde{O}(\sqrt{N}/ε)O(N​/ε) in favorable regimes and reducing tomography to estimating only KKK coefficients instead of NNN amplitudes. In particular, for pure-state tomography with m=O(N)m=O(N)m=O(N) dictionary vectors and sparsity K=O~(1)K=\widetilde{O}(1)K=O(1) on a well-conditioned subdictionary, this circumvents the Ω~(N/ε)\widetildeΩ(N/ε)Ω(N/ε) lower bound that holds in the dense, orthonormal-dictionary setting, without contradiction, by leveraging sparsity together with non-orthogonality. Beyond tomography, we analyze QOMP in the QRAM model, where it yields polynomial speedups over classical OMP implementations, and provide a quantum algorithm to estimate the mutual incoherence of a dictionary of mmm vectors in O(m/ε)O(m/ε)O(m/ε) queries, improving over both deterministic and quantum-inspired classical methods.