arXiv:2609.37926

Optimal Quantum Junta Testing without Inverse Queries

Jinge Bao, Minbo Gao, Penghui Yao

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations

Abstract

We study the query complexity of testing quantum juntas. Given an unknown $n$-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most $k$ qubits or is $\varepsilon$-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U$, but not to $U^\dagger$ or controlled-$U$. We give tight bounds for both unitary and channel junta testing. For sufficiently large $k$, $n \ge 2k$, and a broad range of $\varepsilon$, both problems have query complexity $Θ\left(k/(\varepsilon^2\log k)\right)$. Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an $\widetilde{O}(k)$ upper bound and a $\widetildeΩ(\sqrt{k})$ lower bound at constant $\varepsilon$, establishing the optimal $Θ(k/\log k)$ query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant $\varepsilon$, they also give a separation between $Θ(k/\log k)$ forward queries and $\widetilde{O}(\sqrt{k})$ queries with inverse access.

Comments: 57 pages, 1 table, 3 algorithms

Related papers

Quantum Advantage in Tolerant Junta Testing

Avishay Tal, Weiqiang Yuan

cs.CCCross-listedarXiv:2606.23194Jun 23, 20260 citations

Tolerant Quantum Junta Testing

Zhaoyang Chen, Lvzhou Li, Jingquan Luo

arXiv:2411.02244Nov 4, 20241 citation

Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen, Qisheng Wang, Zhicheng Zhang

quant-pharXiv:2604.26900Leibniz international proceedings in informaticsApr 30, 20260 citations

On Testing and Learning Quantum Junta Channels

Zongbo Bao, Penghui Yao

arXiv:2305.12097IEEE Transactions on Pattern Analysis and Machine IntelligenceJan 13, 20252 citations

Lower Bounds for Unitary Property Testing with Proofs and Advice

Jordi R. Weggemans

arXiv:2401.07912QuantumApr 18, 20253 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

quant-pharXiv:2608.02600Aug 4, 20260 citations

arXiv:2609.37926

Optimal Quantum Junta Testing without Inverse Queries

Jinge Bao, Minbo Gao, Penghui Yao

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations

arXiv HTML PDF

Abstract

We study the query complexity of testing quantum juntas. Given an unknown

n

-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most

k

qubits or is

\varepsilon

-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to

U

, but not to

U^\dagger

or controlled-

U

. We give tight bounds for both unitary and channel junta testing. For sufficiently large

k

n \ge 2k

, and a broad range of

\varepsilon

, both problems have query complexity

Θ\left(k/(\varepsilon^2\log k)\right)

. Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an

\widetilde{O}(k)

upper bound and a

\widetildeΩ(\sqrt{k})

lower bound at constant

\varepsilon

, establishing the optimal

Θ(k/\log k)

query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant

\varepsilon

, they also give a separation between

Θ(k/\log k)

forward queries and

\widetilde{O}(\sqrt{k})

queries with inverse access.

Comments: 57 pages, 1 table, 3 algorithms

Related papers

Quantum Advantage in Tolerant Junta Testing

Avishay Tal, Weiqiang Yuan

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$ -junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$ -junta testing is as follows: given parameters $(k, ε_1, ε_2)$ , with $0\le ε_1<ε_2 \le 1/2$ , and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$ -close to some $k$ -junta or $ε_2$ -far from every $k$ -junta. We show the quantum advantage for a range of parameters close to $1/2$ , for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$ . The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$ -juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$ -juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, ε_1, ε_2)$, with $0\le ε_1<ε_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$-close to some $k$-junta or $ε_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.

cs.CCCross-listedarXiv:2606.23194Jun 23, 20260 citations

Tolerant Quantum Junta Testing

Zhaoyang Chen, Lvzhou Li, Jingquan Luo

Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is $ε_1$ -close to some quantum $k$ -junta or is $ε_2$ -far from any quantum $k$ -junta, where an $n$ -qubit unitary $U$ is called a quantum $k$ -junta if it only non-trivially acts on just $k$ of the $n$ qubits. More specifically, we present a tolerant tester with $ε_1 = \frac{\sqrtρ}{8} ε$ , $ε_2 = ε$ , and $ρ\in (0,1)$ , and the query complexity is $O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)$ , which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to $U^\dagger$ , whereas this is usually required in the literature.Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is $ε_1$-close to some quantum $k$-junta or is $ε_2$-far from any quantum $k$-junta, where an $n$-qubit unitary $U$ is called a quantum $k$-junta if it only non-trivially acts on just $k$ of the $n$ qubits. More specifically, we present a tolerant tester with $ε_1 = \frac{\sqrtρ}{8} ε$, $ε_2 = ε$, and $ρ\in (0,1)$, and the query complexity is $O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)$, which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to $U^\dagger$, whereas this is usually required in the literature.

arXiv:2411.02244Nov 4, 20241 citation

Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen, Qisheng Wang, Zhicheng Zhang

We consider the problem of quantum channel certification to unitary, where one is given access to an unknown $d$ -dimensional channel $\mathcal{E}$ , and wants to test whether $\mathcal{E}$ is equal to a target unitary channel or is $\varepsilon$ -far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that: (i) $Θ(d/\varepsilon^2)$ queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). (ii) $Θ(d/\varepsilon)$ queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). (iii) $Θ(\sqrt{d}/\varepsilon)$ queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026). This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.We consider the problem of quantum channel certification to unitary, where one is given access to an unknown $d$-dimensional channel $\mathcal{E}$, and wants to test whether $\mathcal{E}$ is equal to a target unitary channel or is $\varepsilon$-far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that: (i) $Θ(d/\varepsilon^2)$ queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). (ii) $Θ(d/\varepsilon)$ queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). (iii) $Θ(\sqrt{d}/\varepsilon)$ queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026). This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.

quant-pharXiv:2604.26900Leibniz international proceedings in informaticsApr 30, 20260 citations

On Testing and Learning Quantum Junta Channels

Zongbo Bao, Penghui Yao

We consider the problems of testing and learning quantum -junta channels, which are -qubit to -qubit quantum channels acting non-trivially on at most out of qubits and leaving the rest of qubits unchanged. We show the following. 1) An -query algorithm to distinguish whether the given channel is -junta channel or is far from any -junta channels, and a lower bound on the number of queries; 2) An -query algorithm to learn a -junta channel, and a lower bound on the number of queries. This partially answers an open problem raised by [1]. In order to settle these problems, we develop a Fourier analysis framework over the space of superoperators and prove several fundamental properties, which extends the Fourier analysis over the space of operators introduced in [2]. The distance metric we consider in this paper is obtained by Fourier analysis, which is essentially the L2-distance between Choi representations. Besides, we introduce INFLUENCE-SAMPLE to replace FOURIER-SAMPLE proposed in(Atici and Servedio, 2007). Our INFLUENCE-SAMPLE includes only single-qubit operations and results in only constant-factor decrease in efficiency.We consider the problems of testing and learning quantum -junta channels, which are -qubit to -qubit quantum channels acting non-trivially on at most out of qubits and leaving the rest of qubits unchanged. We show the following. 1) An -query algorithm to distinguish whether the given channel is -junta channel or is far from any -junta channels, and a lower bound on the number of queries; 2) An -query algorithm to learn a -junta channel, and a lower bound on the number of queries. This partially answers an open problem raised by [1]. In order to settle these problems, we develop a Fourier analysis framework over the space of superoperators and prove several fundamental properties, which extends the Fourier analysis over the space of operators introduced in [2]. The distance metric we consider in this paper is obtained by Fourier analysis, which is essentially the L2-distance between Choi representations. Besides, we introduce INFLUENCE-SAMPLE to replace FOURIER-SAMPLE proposed in(Atici and Servedio, 2007). Our INFLUENCE-SAMPLE includes only single-qubit operations and results in only constant-factor decrease in efficiency.

arXiv:2305.12097IEEE Transactions on Pattern Analysis and Machine IntelligenceJan 13, 20252 citations

Lower Bounds for Unitary Property Testing with Proofs and Advice

Jordi R. Weggemans

In unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary and has to decide whether it satisfies some property. We propose a new technique for proving lower bounds on the quantum query complexity of unitary property testing and related problems, which utilises its connection to unitary channel discrimination. The main advantage of this technique is that all obtained lower bounds hold for any C -tester with C⊆QMA(2)/qpoly , showing that even having access to both (unentangled) quantum proofs and advice does not help for many unitary property testing problems. We apply our technique to prove lower bounds for problems like quantum phase estimation, the entanglement entropy problem, quantum Gibbs sampling and more, removing all logarithmic factors in the lower bounds obtained by the sample-to-query lifting theorem of Wang and Zhang (2023). As a direct corollary, we show that there exist quantum oracles relative to which QMA(2)⊅SBQP and QMA/qpoly⊅SBQP . The former shows that, at least in a black-box way, having unentangled quantum proofs does not help in solving problems that require high precision.In unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary and has to decide whether it satisfies some property. We propose a new technique for proving lower bounds on the quantum query complexity of unitary property testing and related problems, which utilises its connection to unitary channel discrimination. The main advantage of this technique is that all obtained lower bounds hold for any C -tester with C⊆QMA(2)/qpoly , showing that even having access to both (unentangled) quantum proofs and advice does not help for many unitary property testing problems. We apply our technique to prove lower bounds for problems like quantum phase estimation, the entanglement entropy problem, quantum Gibbs sampling and more, removing all logarithmic factors in the lower bounds obtained by the sample-to-query lifting theorem of Wang and Zhang (2023). As a direct corollary, we show that there exist quantum oracles relative to which QMA(2)⊅SBQP and QMA/qpoly⊅SBQP . The former shows that, at least in a black-box way, having unentangled quantum proofs does not help in solving problems that require high precision.

arXiv:2401.07912QuantumApr 18, 20253 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$ , where $ρ$ is an unknown $d$ -dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$ , combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is $Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right),$ and the sample complexity of spectrum estimation is $Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right).$ In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$, where $ρ$ is an unknown $d$-dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), \] and the sample complexity of spectrum estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). \] In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.

quant-pharXiv:2608.02600Aug 4, 20260 citations

We study the query complexity of testing quantum juntas. Given an unknown

n

-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most

k

qubits or is

\varepsilon

-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to

U

, but not to

U^\dagger

or controlled-

U

. We give tight bounds for both unitary and channel junta testing. For sufficiently large

k

n \ge 2k

, and a broad range of

\varepsilon

, both problems have query complexity

Θ\left(k/(\varepsilon^2\log k)\right)

\widetilde{O}(k)

upper bound and a

\widetildeΩ(\sqrt{k})

lower bound at constant

\varepsilon

, establishing the optimal

Θ(k/\log k)

\varepsilon

, they also give a separation between

Θ(k/\log k)

forward queries and

\widetilde{O}(\sqrt{k})

queries with inverse access.

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant

k

-junta testing with high precision can be solved using

\mathrm{poly}(k)

quantum queries, whereas any classical algorithm requires at least

k^{Ω(\log k)}

queries. The problem of tolerant

k

-junta testing is as follows: given parameters

(k, ε_1, ε_2)

, with

0\le ε_1<ε_2 \le 1/2

, and black-box access to a Boolean function

f

(defined on

n

variables), distinguish whether

f

ε_1

-close to some

k

-junta or

ε_2

-far from every

k

-junta. We show the quantum advantage for a range of parameters close to

1/2

, for example,

ε_1 = 1/2-1/k

and

ε_2 = 1/2-1/(2k^2)

. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most

ε_1

k

-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick

k

out of

n

coordinates, and for each fixing of the

k

coordinates, the

2^{n-k}

values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to

k

-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making

k^{o(\log k)}

queries.

ε_1

-close to some quantum

k

-junta or is

ε_2

-far from any quantum

k

-junta, where an

n

-qubit unitary

U

is called a quantum

k

-junta if it only non-trivially acts on just

k

of the

n

qubits. More specifically, we present a tolerant tester with

ε_1 = \frac{\sqrtρ}{8} ε

ε_2 = ε

, and

ρ\in (0,1)

, and the query complexity is

O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)

, which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to

U^\dagger

, whereas this is usually required in the literature.

We consider the problem of quantum channel certification to unitary, where one is given access to an unknown

d

-dimensional channel

\mathcal{E}

, and wants to test whether

\mathcal{E}

is equal to a target unitary channel or is

\varepsilon

-far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that: (i)

Θ(d/\varepsilon^2)

queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). (ii)

Θ(d/\varepsilon)

queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). (iii)

Θ(\sqrt{d}/\varepsilon)

queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026). This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form

\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d

, where

ρ

is an unknown

d

-dimensional quantum state and

φ

is a given function. A master theorem is established that derives sample complexity lower bounds for estimating

\mathcal{L}_φ(ρ)

from properties of

φ

, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is

Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right),

and the sample complexity of spectrum estimation is

Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right).

In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.