REVIEW 6 minor 38 references
The suboptimality ratio of projective measurements restricted to low-rank subspaces
T0 review · 0 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read This paper proves that restricting projective measurements to a low-rank subspace costs at most a polylogarithmic factor in the subspace dimension, with no dependence on the ambient dimension.
desk verdict The bound is real and Eq. (92) survives the stress-test; the paper's actual flaw is a wrong justification, not a false statement. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is a decomposition of a restricted projective measurement into weighted projective measurements over the low-rank subspace $S$. Given a projective measurement $P$ on $H$, its projectors projected onto $S$ form a Parseval frame $\{|v_i\rangle\}$ with $\sum_i |v_i\rangle\langle v_i| = 1_S$; splitting this frame into $T$ equal blocks gives weight matrices $L_t = \sum_j |v_{r(t-1)+j}\rangle\langle e_j|$, so that $\operatorname{Tr}[\rho P[\tau]] = \sum_t \operatorname{Tr}[\rho Q_{L_t}[\tau]]$ with $\sum_t L_t L_t^\dagger = 1_S$. The argument then randomizes: with i.i.d. Gaussians $g_t$, the operator $\hat L = \sum_t g_t L_t$ has variance controlled by the operator norm of $L = \sum_t L_t^\dagger L_t$, which the probabilistic method bounds by $O(\log r)$ through a delicate moment count of cycles in random partitions. A complex-interpolation inequality extracts the weight at cost $\|L\|_{\mathrm{op}}^4$, and Gaussian concentration supplies $\mathbb{E}\|\hat L\|_{\mathrm{op}}^4 \le c\log(r)^4$.
What would settle it
Exhibit, for arbitrarily large $r$, a Parseval frame of $S$ for which every permutation and phase choice yields an equipartition whose averaged overlap matrix has operator norm $\omega(\log r)$; Proposition 1 would be false and Theorem 1 would not follow from the submitted proof. A concrete route: take the frame with one block equal to the identity ($L_1=1_S$), where the paper's own analysis gives expected operator norm $\approx \log r/\log\log r$, and check whether the supremum over partitions crosses the $\log r$ threshold.
Extended reading notes
Core claim
Define $K_{n,r}$ as the smallest constant such that for every pair of density matrices $\rho,\tau$ supported on an $r$-dimensional subspace $S$ of an $n$-dimensional Hilbert space, the optimal projective-measurement overlap over all of $H$ is at most $K_{n,r}$ times the optimal overlap using only projective measurements aligned with $S$. The paper establishes $K_{n,r}\le c\log(r)^4$ for all $n\ge r\ge 2$. The proof decomposes an arbitrary measurement on $H$ into $T=\lceil n/r\rceil$ weighted measurements on $S$ whose weight matrices come from an equipartition of a Parseval frame, shows via the probabilistic method that a permutation and phase choice make the averaged Gram matrix have operator norm $O(\log r)$, randomizes the weights with independent Gaussians to decouple the $T$ terms, uses Gaussian concentration to control the resulting random operator, and finally strips the weights with a new complex-interpolation trace inequality. Each step preserves the projective-measurement structure, which is what makes the bound about measurements rather than about general quantum channels.
Load-bearing premise
The proof rests on the claim that the vectors obtained by projecting a measurement onto the low-rank subspace can always be reordered and phase-shifted so that, when split into equal blocks, their averaged overlap matrix has operator norm at most a constant times $\log r$; if the combinatorial counting argument behind this estimate fails, the variance control and with it the polylog bound collapse.
Editorial extensions
If this is right
- For the Procrustes problem, optimizing over subspace-aligned measurements approximates the full optimum up to a factor $c\log(r)^4$, so measurement policies can be chosen in the low-rank space.
- The bound is independent of the ambient dimension $n$: adding unused dimensions to the Hilbert space does not worsen the suboptimality ratio.
- Corollary 1 gives a concrete, though not sharp, approximation inequality for the expected Frobenius-distance minimization.
- The polylogarithmic exponent $4$ arises from the dimensional factor in Gaussian matrix concentration, and the paper notes that improving the bound would require exploiting extra low-rank structure in the weight matrices.
- Numerical experiments with manifold gradient ascent suggest $K_r\approx 1$ for $r\le 20$, and the paper poses the conjecture that $K_{n,r}\le C$ for a universal constant $C\ge 1$ (possibly $C=1$).
Reading between the lines
- If the paper's conjecture of a bounded $K_{n,r}$ holds, the polylogarithmic slack in Theorem 1 is an artifact of the proof rather than a real cost; a concrete test would push numerical optimization to $r\gg 20$ with global search or semidefinite bounds to check whether $K_r>1$ appears.
- The interpolation step (Proposition 2) is stated for projective measurements but the proof uses only that the $Q_i$ are symmetric rank-one operators, so the same suboptimality bound should extend to rank-one POVMs and symmetric Kraus representations; if so, similar guarantees would hold for measurement implementations that simulate POVMs by postselection.
- The combinatorial moment bound (Lemma 2) controls the averaged Gram matrix of arbitrary Parseval frames under equipartitions, independent of the Procrustes objective, so it could be reused in other frame-restricted quantum optimization problems such as state discrimination or tomography with block-structured instruments.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the suboptimality ratio K_{n,r} for a Procrustes problem in which the optimization is over projective measurements aligned with a low-rank subspace S of dimension r inside an ambient space H of dimension n. The main result, Theorem 1 (Eq. (21)), states that K_{n,r} is bounded by c log(r)^4 uniformly in n. The proof has six steps: reduction of a projective measurement on H to a sum of T weighted projective measurements on S (Lemma 1); existence of a permutation and phase choice for which the associated frame Gram operator has operator norm O(log r) (Proposition 1, based on the moment estimate Lemma 2 in Appendix A); randomization with Gaussian weights (Lemma 3); concentration of the random matrix norm via Tropp's inequality (Lemmas 7, 8, Corollary 2); an interpolation inequality that extracts the weight at a cost ||L||_op^4 (Proposition 2); and a final combination, with the small-n case handled by enlarging the ambient space. The paper also includes numerical experiments and a conjecture that K_{n,r}=O(1).
Significance. If correct, Theorem 1 is a strong and clean result: the suboptimality of low-rank-aligned projective measurements is independent of the ambient dimension and only polylogarithmic in the rank r. The proof is essentially self-contained, deriving the bound from standard external results (Lieb's trace convexity, the Hadamard three-lines theorem, and Tropp's matrix concentration inequalities) together with new technical ingredients, notably the probabilistic equipartition of Parseval frames and the operator-norm moment estimates in Lemma 2 and Appendix A. There are no fitted constants and no circular dependence on the target inequality. I also checked the specific stress-test concern about Proposition 2, Eq. (92): the displayed equality is in fact true, although the proof should justify it more explicitly. The main caveat is that several displayed formulas in the combinatorial part are misprinted, which currently makes parts of Appendix A formally incorrect as written; these appear to be typographical and locally fixable.
minor comments (6)
- [§4.5, Eq. (92)] The step labeled 'Lemma 9' is too terse and, as written, invites the objection that Lemma 9 applies to one copy of K while the integrand contains two powers of \tilde L^{-2it}. The equality is true, but it should be proved explicitly: for K=\tilde L^2\ge 0 with \|K\|_{op}\le 1, the Cauchy measure \mu(dt)=dt/(\pi(1+t^2)) satisfies \int K^{-it}\otimes K^{-it}\,\mu(dt)=K\otimes K, because -\log K has nonnegative eigenvalues and the Fourier transform of \mu is e^{-|x|}. I recommend adding this one-line verification so that the application to the product of two traces is transparent.
- [Appendix A, Lemma 14 and Lemma 16-17] Several displayed probability and weight formulas are missing a reciprocal denominator. For example, in Lemma 14(ii), Eq. (122) as printed gives a value that can exceed 1; the correct expression is C_{V,\Gamma}= r\big/\big[(\tbinom{Tr}{n(V)})(\tbinom{n(\Gamma)}{z(\Gamma)})\big], matching the counting argument in the proof. The same missing reciprocal appears in Eqs. (124), (150), (157), and (158). These are almost certainly typographical, but they must be corrected because the subsequent asymptotic estimates in Lemma 17 rely on the reciprocal form.
- [§4.2, Lemma 2 and Proposition 1] The notation in Eq. (45) is ambiguous: the first term should read r k^k (not r^k k). The proof of Proposition 1 only goes through with r k^k, since F(k)^{1/k} is then O(r^{1/k} k)=O(log r). Please make the exponent explicit throughout, including Lemma 19 and the proof of Proposition 1.
- [§3, Corollary 1, Eq. (22)] The trace term Tr[\tau Q[\rho]] appearing on the left-hand side is not quantified. The inequality needs a clearly specified Q (e.g., any fixed feasible Q, or an appropriate extremal choice), otherwise the statement is not well posed.
- [§5, Numerical experiments] The paragraph after Eq. (104) correctly notes that \hat K_r can fall below 1 and that convergence is not certified; this should be stated as a limitation of the numerics in the main text, not only as an aside, since Figure 1 might otherwise be read as evidence for Conjecture 5 with C=1.
- [References] Reference [25] contains corrupted author names ('Micha/suppress l Oszmaniec', 'Zbigniew Pucha/suppress la'); the correct names are Micha\l{} Oszmaniec and Zbigniew Pucha\l{}a. Please also check other author names for OCR-style corruption.
Circularity Check
No significant circularity: the log^4 bound is derived from stated lemmas, not fitted or assumed as an input.
full rationale
The derivation chain for Theorem 1 (Eq. 21) is self-contained. Lemma 1 is a Naimark-style decomposition with an explicit proof; Proposition 1 is proved from the moment estimate Lemma 2, whose proof counts cycle factors without importing the target inequality; Lemma 3 randomizes the weighted measurements using only Gaussian identities and trace convexity; Corollary 2 follows from Tropp's concentration inequality [34] together with the frame normalizations (33) and (49); Proposition 2 is an independent complex-interpolation statement proved via Lemma 9 and the Hadamard three-lines theorem; and the final assembly in (95) combines these bounds without defining K_{n,r} through the conclusion. There is no fitted parameter, no self-citation chain (the cited sources are external, e.g. [23, 29, 34]), and no existence claim rests on an assumption equivalent to the theorem's polylogarithmic conclusion. A reviewer's concern about the application of Lemma 9 around Eq. (92), if valid, would be a correctness gap rather than circularity: even a flawed step would not make the claimed bound equal to its inputs by construction. Accordingly the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- domain assumption Finite-dimensional Hilbert space formalism, density matrices, and projective measurements as in Eqs. (10)-(11).
- standard math Lieb's trace convexity inequality (Lemma 5) as cited from [23].
- standard math Hadamard three-lines theorem (Lemma 10) from [29].
- standard math Gaussian matrix concentration bound (Lemma 7) adapted from Tropp [34].
- standard math Probabilistic method and method of moments.
Cite this review
Pith. "Pith review of The suboptimality ratio of projective measurements restricted to low-rank subspaces." pith.science (2026). https://pith.science/paper/LUQA7ZTJ
@misc{pith2026241212413,
author = {Pith},
title = {Pith review of: The suboptimality ratio of projective measurements restricted to low-rank subspaces},
year = {2026},
howpublished = {\url{https://pith.science/paper/LUQA7ZTJ}},
note = {Machine review of arXiv:2412.12413}
}
read the original abstract
Limitations in measurement instruments can hinder the implementation of some quantum algorithms. Understanding the suboptimality of such measurements with restrictions may then lead to more efficient measurement policies. In this paper, we theoretically examine the suboptimality arising from a Procrustes problem for minimizing the average distance between two fixed quantum states when one of the states has been measured by a Projective Measurement (PM). Specifically, we compare optima when we can only use PMs that are aligned with a low-rank subspace where the quantum states are supported, and when we can measure with the full set of PMs. For this problem, we show that the suboptimality ratio is independent of the dimension of the full space, and is at most polylogarithmic in the dimension of the low-rank subspace. In the proof of this result, we use a probabilistic approach and the main techniques include trace inequalities related to projective measurements, and operator norm bounds for equipartitions of Parseval frames, which are of independent interest.
Figures
Reference graph
Works this paper leans on
-
[1]
Absil, Robert Mahony, and Rodolphe Sepulchre
P-A. Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2008
work page 2008
-
[2]
Noga Alon and Joel H. Spencer. The probabilistic method. John Wiley & Sons, 2016
work page 2016
-
[3]
Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic forms on graphs. Inventiones mathematicae, 163(3):499–522, 2006
work page 2006
-
[4]
On the non-symmetric semidefinite procrustes problem
Mohit Kumar Baghel, Nicolas Gillis, and Punit Sharma. On the non-symmetric semidefinite procrustes problem. Linear Algebra and its Applications , 648:133–159, 2022
work page 2022
-
[5]
Approximating the little grothendieck problem over the orthogonal and unitary groups
Afonso S Bandeira, Christopher Kennedy, and Amit Singer. Approximating the little grothendieck problem over the orthogonal and unitary groups. Mathematical programming, 160:433–475, 2016
work page 2016
-
[6]
Procrustes problems in riemannian manifolds of positive definite matrices
Rajendra Bhatia and Marco Congedo. Procrustes problems in riemannian manifolds of positive definite matrices. Linear Algebra and its Applications , 563:440–445, 2019
work page 2019
-
[7]
Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D’Ariano, Stefano Facchini, and Paolo Perinotti. Optimal quantum tomography. IEEE Journal of Selected Topics in Quantum Electronics, 15(6):1646–1660, 2009
work page 2009
-
[8]
The Grothendieck inequality revisited, volume 232
Ron Blei. The Grothendieck inequality revisited, volume 232. American Mathematical Society, 2014
work page 2014
Show all 38 references
-
[9]
Briegel, David E
Hans J. Briegel, David E. Browne, Wolfgang D¨ ur, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. Nature Physics, 5(1):19–26, 2009
2009
-
[10]
Grothendieck inequalities for semidefinite programs with rank constraint
Jop Bri¨ et, Fernando M´ ario de Oliveira Filho, and Frank Vallentin. Grothendieck inequalities for semidefinite programs with rank constraint. Theory OF Computing , 10(4):77–105, 2014
2014
-
[11]
Quantum state discrimination
Anthony Chefles. Quantum state discrimination. Contemporary Physics, 41(6):401–424, 2000
2000
-
[12]
Cirel’son
Boris S. Cirel’son. Quantum generalizations of bell’s inequality. Letters in Mathematical Physics, 4:93–100, 1980
1980
-
[13]
Orthogonalization of positive operator valued measures
Mikael de La Salle. Orthogonalization of positive operator valued measures. arXiv preprint arXiv:2103.14126, 2021
2021 arXiv
-
[14]
Solving constrained procrustes problems: a conic opti- mization approach
Ter´ ezia Fulov´ a and M´ aria Trnovsk´ a. Solving constrained procrustes problems: a conic opti- mization approach. arXiv preprint arXiv:2304.14961 , 2023
2023 arXiv
-
[15]
Gonz´ alez-Guill´ en, Marius Junge, and Ion Nechita
Carlos E. Gonz´ alez-Guill´ en, Marius Junge, and Ion Nechita. On the spectral gap of random quantum channels. arXiv preprint arXiv:1811.08847 , 2018
2018 arXiv
-
[16]
Gower and Garmt B
John C. Gower and Garmt B. Dijksterhuis. Procrustes problems, volume 30. OUP Oxford, 2004
2004
-
[17]
Hastings
Matthew B. Hastings. Random unitaries give quantum expanders. Physical Review A—Atomic, Molecular, and Optical Physics , 76(3):032315, 2007
2007
-
[18]
Choice of measurement as the signal
Amir Kalev, Ady Mann, and Michael Revzen. Choice of measurement as the signal. Physical Review Letters, 110(26):260502, 2013
2013
-
[19]
Constantes de grothendieck et fonctions de type positif sur les spheres
Jean-Louis Krivine. Constantes de grothendieck et fonctions de type positif sur les spheres. S´ eminaire Maurey-Schwartz, pages 1–17, 1978
1978
-
[20]
Optimal quantum (tensor product) expanders from unitary designs
C´ ecilia Lancien. Optimal quantum (tensor product) expanders from unitary designs. arXiv preprint arXiv:2409.17971, 2024
2024
-
[21]
Approximating quantum channels by completely positive maps with small kraus rank
C´ ecilia Lancien and Andreas Winter. Approximating quantum channels by completely positive maps with small kraus rank. Quantum, 8:1320, 2024. 20
2024
-
[22]
Limiting spectral distribution of random self-adjoint quantum channels
C´ ecilia Lancien, Patrick Oliveira Santos, and Pierre Youssef. Limiting spectral distribution of random self-adjoint quantum channels. Mathematical Physics, Analysis and Geometry , 27(3): 15, 2024
2024
-
[23]
Elliott H. Lieb. Convex trace functions and the wigner-yanase-dyson conjecture. Les rencontres physiciens-math´ ematiciens de Strasbourg-RCP25, 19:0–35, 1973
1973
-
[24]
Choice of measurement as the secret
Bin Liu, Fei Gao, Su-Juan Qin, Wei Huang, Feng Liu, and Qiao-Yan Wen. Choice of measurement as the secret. Physical Review A, 89(4):042318, 2014
2014
-
[25]
Maciejewski, and Zbigniew Pucha/suppress la
Micha/suppress l Oszmaniec, Filip B. Maciejewski, and Zbigniew Pucha/suppress la. Simulating all quantum measurements using only projective measurements and postselection. Physical Review A, 100 (1):012351, 2019
2019
-
[26]
Quantum control by von neumann measurements
Alexander Pechen, Nikolai Il’in, Feng Shuang, and Herschel Rabitz. Quantum control by von neumann measurements. Physical Review A, 74(5):052102, 2006
2006
-
[27]
Control landscapes for two-level open quantum systems
Alexander Pechen, Dmitrii Prokhorenko, Rebing Wu, and Herschel Rabitz. Control landscapes for two-level open quantum systems. Journal of Physics A: Mathematical and Theoretical , 41 (4):045205, 2008
2008
-
[28]
Balls into bins
Martin Raab and Angelika Steger. “Balls into bins”—a simple and tight analysis. In Inter- national Workshop on Randomization and Approximation Techniques in Computer Science , pages 159–170. Springer, 1998
1998
-
[29]
II: Fourier Analysis, Self-Adjointness , volume 2
Michael Reed and Barry Simon. II: Fourier Analysis, Self-Adjointness , volume 2. Elsevier, 1975
1975
-
[30]
Sch¨ onemann
Peter H. Sch¨ onemann. A generalized solution of the orthogonal procrustes problem.Psychome- trika, 31(1):1–10, 1966
1966
-
[31]
Richard P. Stanley. Enumerative combinatorics volume 1 second edition. Cambridge studies in advanced mathematics, 2011
2011
-
[32]
Multivariate trace inequalities
David Sutter, Mario Berta, and Marco Tomamichel. Multivariate trace inequalities. Commu- nications in Mathematical Physics , 352:37–58, 2017
2017
-
[33]
Topics in random matrix theory , volume 132
Terence Tao. Topics in random matrix theory , volume 132. American Mathematical Soc., 2012
2012
-
[34]
Tropp et al
Joel A. Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends® in Machine Learning, 8(1-2):1–230, 2015
2015
-
[35]
Shayne F.D. Waldron. An introduction to finite tight frames . Springer, 2018
2018
-
[36]
Quantum state transformation by optimal projective measurements
Yaoxiong Wang, Rebing Wu, Xin Chen, Yunjian Ge, Junhui Shi, Herschel Rabitz, and Feng Shuang. Quantum state transformation by optimal projective measurements. Journal of mathematical chemistry, 49:507–519, 2011
2011
-
[37]
Joong-Ho Won, Hua Zhou, and Kenneth L. Lange. Orthogonal trace-sum maximization: Applications, local algorithms, and global optimality. SIAM journal on matrix analysis and applications : a publication of the Society for Industrial and Applied Mathematics , 42 2:859–882, 2018. ...
2018
-
[38]
and each ℓ = (ℓ1,...,ℓ k)∈ L(k) will track the matrix indices in the expansion of EΘ [ Tr [k∏ j=1 Lπ ℓj(Θ) ]]
Indeed, there must be 4 transitions between partition sets. and each ℓ = (ℓ1,...,ℓ k)∈ L(k) will track the matrix indices in the expansion of EΘ [ Tr [k∏ j=1 Lπ ℓj(Θ) ]] . (114) Forℓ∈ L(k), we will denote the set of different indices appearing in ℓ byN(ℓ) =∪k i=1{ℓi}, and n(ℓ)...
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.