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:2610.17163

Bosonic unstructured search: quantum enhancement without entanglement

Yu-Xin Wang, Erfan Abbasgholinejad, Supratik Sarkar, Sharoon Austin, Andrew M. Childs, Alexey V. Gorshkov, Mohammad Hafezi

quant-phSubmitted Oct 12, 2026• Announced Oct 13, 2026• 0 citations
arXivHTMLPDF

Abstract

We consider unstructured search using multimode bosonic quantum systems under energy constraints. The task is to locate an unknown marked mode among $N$ possibilities using arbitrary control, subject to a time-averaged mean-boson-number budget $n_{\text{b}}\gg 1$. We analyze a continuous-time phase-shift oracle of strength $B_{0}$, with cost given by the total oracle time, and a discrete oracle with fixed phase $φ_{0}$, with cost given by the number of queries. We give algorithms that identify the target with query complexity $O(\sqrt{N}/{n_{\text{b}}}B_{0})$ for continuous-time oracles or $O(\sqrt{N}/n_{\text{b}} |{\sin(φ_{0}/{2})}|)$ for discrete oracles with $n_{\text{b}} |{\sin(φ_{0}/{2})}|=O(1)$. In contrast, for discrete oracles with $n_{\text{b}} |{\sin(φ_{0}/{2})}|=Ω(1)$, we provide an algorithm using $O(\max\{1,\sqrt{N/n_{\text{b}}|{\sin(φ_{0}/{2})}|}\})$ queries. We also prove matching lower bounds on the query complexity, showing that these algorithms are asymptotically optimal. Furthermore, we show that, in the absence of loss, non-Gaussianity is necessary to achieve the optimal joint query scaling in $N$ and $n_{\text{b}}$, but entanglement is not. Under uniform boson loss at rate $γ$, we prove a query lower bound of $Ω( γN / n _{\text{b}} B_{0}^{2} )$, attained for $γ= Ω(B_{0} \sqrt{n _{\text{b}}/N})$ using coherent-state probes. Finally, we propose experimental implementations using multipass optical microscopy or superconducting circuits as potential routes to speeding up imaging or device calibration with a low boson-number budget.

AI Summary

The paper studies identification of one marked mode among $N$ bosonic modes, where the mark applies a number-dependent phase shift. It allows arbitrary controls, ancillas and adaptive measurements, subject to a time-averaged total mean-boson-number budget $n_b\gg1$. Cost counts oracle interaction time or fixed-phase queries, not control overhead. For the continuous-time oracle $e^{-iB_0t\hat n_x}$ with uniform boson loss rate $\gamma$, it establishes the optimal scaling $T=\Theta(\max\{\sqrt N/(n_bB_0),N\gamma/(n_bB_0^2)\})$. Loss therefore changes the mode-number scaling once $\gamma$ exceeds order $B_0/\sqrt N$. Without loss, both a W-like superposition of multimode Fock states and a fully separable protocol using local vacuum–Fock superpositions attain the optimum. Strategies whose unconditional probe state remains Gaussian obey the stronger bound $T=\Omega(B_0^{-1}\min\{\sqrt{N/n_b},N/n_b\})$, with matching constructions. Coherent probes attain the general lossy bound when $\gamma=\Omega(B_0\sqrt{n_b/N})$. For fixed-phase queries, writing $q=n_b|\sin(\phi_0/2)|$, the optimal query count is $\Theta(\max\{1,\sqrt N/\min(q,\sqrt q)\})$, distinguishing discrete queries from freely adjustable interrogation times. The lower bounds compare distinguishability between oracle trajectories using positivity and mean-energy constraints; Gaussian bounds use photon-number moment inequalities, while the loss proof uses a split-environment dilation. Optical and superconducting-circuit implementations are proposed, not demonstrated. Practical limitations include nonlinear-control requirements, architecture-dependent parallelization overhead and loss sensitivity. The Gaussian exclusion does not cover arbitrary outcome-dependent feedforward, and the lossy lower bound assumes finite instantaneous second photon-number moments.

No sign of AI-generated textStrong assumptions

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum Search with Noisy Oracle

Ansis Rosmanis

We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability $p>0$ completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum $\mathrm{O}(\sqrt{n})$-query algorithms in this setting, even for constant $p$. We show that, for all $p\le 0.99$, the quantum noisy-query complexity of the unstructured search is $\tildeΘ(\max\{np,\sqrt{n}\})$. The lower bound $Ω(\max\{np,\sqrt n\})$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.

arXiv:2309.14944•Sep 26, 2023•17 citations

Noisy Quantum Query Complexity via Fractional Block Sensitivity

Mehil Agarwal, Shravas Rao, Fang Song

We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ($\operatorname{fbs}$). For a negligent oracle that applies the correct query with probability $1-p$, we prove a lower bound in terms of $\operatorname{fbs}(f,0^n)$. We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function $f$ can be transformed into a partial function $f'$ whose negligent query complexity essentially preserves the quantum query complexity of $f$. This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of $\operatorname{fbs}(f)$ for partial functions in this model. For two other models, we obtain general lower bounds in terms of $\operatorname{fbs}(f)$ for all Boolean functions. For hybrid algorithms using $Q$ coherent and $C$ classical queries, we prove the tradeoff $C+Q^2=Ω(\operatorname{fbs}(f))$. For an IID dephasing noisy model where each query dephases the query-index register at rate $p$ independently, we prove $Ω\!\left(p\,\operatorname{fbs}(f)\right)$ queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by $\operatorname{fbs}(f)$. Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.

quant-pharXiv:2610.00506•Oct 2, 2026•0 citations

Unstructured search by random and quantum walk

Thomas G. Wong

The task of finding an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer and $O(\sqrt{N})$ queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large $N$, the random walks converge to the same evolution, both taking $N \ln(1/\epsilon)$ time to reach a success probability of $1-\epsilon$. In contrast, the discrete-time quantum walk asymptotically takes $\pi\sqrt{N}/2\sqrt{2}$ timesteps to reach a success probability of $1/2$, while the continuous-time quantum walk takes $\pi\sqrt{N}/2$ time to reach a success probability of $1$.

arXiv:2011.14533•Quantum Information and Computation•Dec 28, 2021•11 citations

Quantum Submodular Maximization

Yonggang Jiang, Xiaoming Sun, Penghui Yao +3 more

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$-approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$-approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$, the query complexity reduces to $O_{\varepsilon,c}(\log n)$, yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.

quant-pharXiv:2610.04560•Oct 6, 2026•0 citations

Efficient learning of bosonic Gaussian unitaries

Marco Fanizza, Iyer, Vishnu, Junseo Lee +2 more

Bosonic Gaussian unitaries are fundamental building blocks of central continuous-variable quantum technologies such as quantum-optic interferometry and bosonic error-correction schemes. In this work, we present the first time-efficient algorithm for learning bosonic Gaussian unitaries with a rigorous analysis. Our algorithm produces an estimate of the unknown unitary that is accurate to small worst-case error, measured by the physically motivated energy-constrained diamond distance. Its runtime and query complexity scale polynomially with the number of modes, the inverse target accuracy, and natural energy parameters quantifying the allowed input energy and the unitary's output-energy growth. The protocol uses only experimentally friendly photonic resources: coherent and squeezed probes, passive linear optics, and heterodyne/homodyne detection. We then employ an efficient classical post-processing routine that leverages a symplectic regularization step to project matrix estimates onto the symplectic group. In the limit of unbounded input energy, our procedure attains arbitrarily high precision using only $2m+2$ queries, where $m$ is the number of modes. To our knowledge, this is the first provably efficient learning algorithm for a multiparameter family of continuous-variable unitaries.

arXiv:2510.05531•Oct 7, 2025•17 citations

What resources are needed for optimal learning of bosonic Gaussian states?

Senrui Chen, Francesco Anna Mele, Marco Fanizza +5 more

Continuous-variable systems enable key quantum technologies in computation, communication, and sensing. Bosonic Gaussian states emerge naturally in various such applications, including gravitational-wave and dark-matter detection. A fundamental question is how to characterize an unknown bosonic Gaussian state from as few samples as possible. Despite decades-long exploration, the ultimate efficiency limit remains unclear. In this work, we study the necessary and sufficient number of copies to learn an $n$-mode Gaussian state, with energy less than $E$, to $\varepsilon$ trace distance with high probability. We prove a lower bound of $Ω(n^3/\varepsilon^2)$ for Gaussian measurements, matching the best known upper bound up to doubly-log energy dependence, and $Ω(n^2/\varepsilon^2)$ for arbitrary measurements. We further show an upper bound of $\widetilde{O}(n^2/\varepsilon^2)$ given that the Gaussian state is promised to be either pure or passive. Interestingly, while Gaussian measurements suffice for nearly optimal learning of pure Gaussian states, non-Gaussian measurements are provably required for optimal learning of passive Gaussian states. Finally, focusing on learning single-mode Gaussian states via non-entangling Gaussian measurements, we provide a nearly tight bound of $\widetildeΘ(E/\varepsilon^2)$ for any non-adaptive schemes, showing adaptivity is indispensable for nearly energy-independent scaling. As a byproduct, we establish sharp bounds on the trace distance between Gaussian states in terms of the total variation distance between their Wigner distributions, and obtain a nearly tight sample complexity bound for learning the Wigner distribution of any Gaussian state to $\varepsilon$ total variation distance. Our results significantly advance quantum learning theory in the bosonic regimes and have practical impact in quantum sensing and benchmarking applications.

quant-pharXiv:2603.18136•Mar 20, 2026•14 citations
We consider unstructured search using multimode bosonic quantum systems under energy constraints. The task is to locate an unknown marked mode among NNN possibilities using arbitrary control, subject to a time-averaged mean-boson-number budget nb≫1n_{\text{b}}\gg 1nb​≫1. We analyze a continuous-time phase-shift oracle of strength B0B_{0}B0​, with cost given by the total oracle time, and a discrete oracle with fixed phase φ0φ_{0}φ0​, with cost given by the number of queries. We give algorithms that identify the target with query complexity O(N/nbB0)O(\sqrt{N}/{n_{\text{b}}}B_{0})O(N​/nb​B0​) for continuous-time oracles or O(N/nb∣sin⁡(φ0/2)∣)O(\sqrt{N}/n_{\text{b}} |{\sin(φ_{0}/{2})}|)O(N​/nb​∣sin(φ0​/2)∣) for discrete oracles with nb∣sin⁡(φ0/2)∣=O(1)n_{\text{b}} |{\sin(φ_{0}/{2})}|=O(1)nb​∣sin(φ0​/2)∣=O(1). In contrast, for discrete oracles with nb∣sin⁡(φ0/2)∣=Ω(1)n_{\text{b}} |{\sin(φ_{0}/{2})}|=Ω(1)nb​∣sin(φ0​/2)∣=Ω(1), we provide an algorithm using O(max⁡{1,N/nb∣sin⁡(φ0/2)∣})O(\max\{1,\sqrt{N/n_{\text{b}}|{\sin(φ_{0}/{2})}|}\})O(max{1,N/nb​∣sin(φ0​/2)∣​}) queries. We also prove matching lower bounds on the query complexity, showing that these algorithms are asymptotically optimal. Furthermore, we show that, in the absence of loss, non-Gaussianity is necessary to achieve the optimal joint query scaling in NNN and nbn_{\text{b}}nb​, but entanglement is not. Under uniform boson loss at rate γγγ, we prove a query lower bound of Ω(γN/nbB02)Ω( γN / n _{\text{b}} B_{0}^{2} )Ω(γN/nb​B02​), attained for γ=Ω(B0nb/N)γ= Ω(B_{0} \sqrt{n _{\text{b}}/N})γ=Ω(B0​nb​/N​) using coherent-state probes. Finally, we propose experimental implementations using multipass optical microscopy or superconducting circuits as potential routes to speeding up imaging or device calibration with a low boson-number budget.
The paper studies identification of one marked mode among NNN bosonic modes, where the mark applies a number-dependent phase shift. It allows arbitrary controls, ancillas and adaptive measurements, subject to a time-averaged total mean-boson-number budget nb≫1n_b\gg1nb​≫1. Cost counts oracle interaction time or fixed-phase queries, not control overhead.
For the continuous-time oracle e−iB0tn^xe^{-iB_0t\hat n_x}e−iB0​tn^x​ with uniform boson loss rate γ\gammaγ, it establishes the optimal scaling T=Θ(max⁡{N/(nbB0),Nγ/(nbB02)})T=\Theta(\max\{\sqrt N/(n_bB_0),N\gamma/(n_bB_0^2)\})T=Θ(max{N​/(nb​B0​),Nγ/(nb​B02​)}). Loss therefore changes the mode-number scaling once γ\gammaγ exceeds order B0/NB_0/\sqrt NB0​/N​. Without loss, both a W-like superposition of multimode Fock states and a fully separable protocol using local vacuum–Fock superpositions attain the optimum. Strategies whose unconditional probe state remains Gaussian obey the stronger bound T=Ω(B0−1min⁡{N/nb,N/nb})T=\Omega(B_0^{-1}\min\{\sqrt{N/n_b},N/n_b\})T=Ω(B0−1​min{N/nb​​,N/nb​}), with matching constructions. Coherent probes attain the general lossy bound when γ=Ω(B0nb/N)\gamma=\Omega(B_0\sqrt{n_b/N})γ=Ω(B0​nb​/N​).
For fixed-phase queries, writing q=nb∣sin⁡(ϕ0/2)∣q=n_b|\sin(\phi_0/2)|q=nb​∣sin(ϕ0​/2)∣, the optimal query count is Θ(max⁡{1,N/min⁡(q,q)})\Theta(\max\{1,\sqrt N/\min(q,\sqrt q)\})Θ(max{1,N​/min(q,q​)}), distinguishing discrete queries from freely adjustable interrogation times.
The lower bounds compare distinguishability between oracle trajectories using positivity and mean-energy constraints; Gaussian bounds use photon-number moment inequalities, while the loss proof uses a split-environment dilation. Optical and superconducting-circuit implementations are proposed, not demonstrated. Practical limitations include nonlinear-control requirements, architecture-dependent parallelization overhead and loss sensitivity. The Gaussian exclusion does not cover arbitrary outcome-dependent feedforward, and the lossy lower bound assumes finite instantaneous second photon-number moments.
We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability p>0p>0p>0 completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum O(n)\mathrm{O}(\sqrt{n})O(n​)-query algorithms in this setting, even for constant ppp. We show that, for all p≤0.99p\le 0.99p≤0.99, the quantum noisy-query complexity of the unstructured search is Θ~(max⁡{np,n})\tildeΘ(\max\{np,\sqrt{n}\})Θ~(max{np,n​}). The lower bound Ω(max⁡{np,n})Ω(\max\{np,\sqrt n\})Ω(max{np,n​}) holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.
We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity (fbs⁡\operatorname{fbs}fbs). For a negligent oracle that applies the correct query with probability 1−p1-p1−p, we prove a lower bound in terms of fbs⁡(f,0n)\operatorname{fbs}(f,0^n)fbs(f,0n). We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function fff can be transformed into a partial function f′f'f′ whose negligent query complexity essentially preserves the quantum query complexity of fff. This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of fbs⁡(f)\operatorname{fbs}(f)fbs(f) for partial functions in this model. For two other models, we obtain general lower bounds in terms of fbs⁡(f)\operatorname{fbs}(f)fbs(f) for all Boolean functions. For hybrid algorithms using QQQ coherent and CCC classical queries, we prove the tradeoff C+Q2=Ω(fbs⁡(f))C+Q^2=Ω(\operatorname{fbs}(f))C+Q2=Ω(fbs(f)). For an IID dephasing noisy model where each query dephases the query-index register at rate ppp independently, we prove Ω ⁣(p fbs⁡(f))Ω\!\left(p\,\operatorname{fbs}(f)\right)Ω(pfbs(f)) queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by fbs⁡(f)\operatorname{fbs}(f)fbs(f). Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.
The task of finding an entry in an unsorted list of NNN elements famously takes O(N)O(N)O(N) queries to an oracle for a classical computer and O(N)O(\sqrt{N})O(N​) queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large NNN, the random walks converge to the same evolution, both taking Nln⁡(1/ϵ)N \ln(1/\epsilon)Nln(1/ϵ) time to reach a success probability of 1−ϵ1-\epsilon1−ϵ. In contrast, the discrete-time quantum walk asymptotically takes πN/22\pi\sqrt{N}/2\sqrt{2}πN​/22​ timesteps to reach a success probability of 1/21/21/2, while the continuous-time quantum walk takes πN/2\pi\sqrt{N}/2πN​/2 time to reach a success probability of 111.
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint kkk on an nnn-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected (1/2−ε)(1/2-\varepsilon)(1/2−ε)-approximation using only Oε(log⁡n)O_\varepsilon(\log n)Oε​(logn) queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above 1/41/41/4 requires Ω(n/log⁡n)Ω(n/\log n)Ω(n/logn) queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a (1−1/e−ε)(1-1/e-\varepsilon)(1−1/e−ε)-approximation using O~ε(min⁡{n,n/k})\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})Oε​(min{n​,n/k}) queries. When k=o(n)k=o(n)k=o(n), our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when k=cnk=cnk=cn for any fixed rational c<1−1/e−εc<1-1/e-\varepsilonc<1−1/e−ε, the query complexity reduces to Oε,c(log⁡n)O_{\varepsilon,c}(\log n)Oε,c​(logn), yielding an exponential separation from the classical Ω(n/log⁡n)Ω(n/\log n)Ω(n/logn) lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of exp⁡(Ω(ε2n))\exp(Ω(\varepsilon^2n))exp(Ω(ε2n)) queries for achieving a ratio beyond 1/2+ε1/2+\varepsilon1/2+ε without constraints, and exp⁡(Ω(ε2k))\exp(Ω(\varepsilon^2k))exp(Ω(ε2k)) queries for exceeding 1−1/e+ε1-1/e+\varepsilon1−1/e+ε when k/n≤εk/n\le\varepsilonk/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.
Bosonic Gaussian unitaries are fundamental building blocks of central continuous-variable quantum technologies such as quantum-optic interferometry and bosonic error-correction schemes. In this work, we present the first time-efficient algorithm for learning bosonic Gaussian unitaries with a rigorous analysis. Our algorithm produces an estimate of the unknown unitary that is accurate to small worst-case error, measured by the physically motivated energy-constrained diamond distance. Its runtime and query complexity scale polynomially with the number of modes, the inverse target accuracy, and natural energy parameters quantifying the allowed input energy and the unitary's output-energy growth. The protocol uses only experimentally friendly photonic resources: coherent and squeezed probes, passive linear optics, and heterodyne/homodyne detection. We then employ an efficient classical post-processing routine that leverages a symplectic regularization step to project matrix estimates onto the symplectic group. In the limit of unbounded input energy, our procedure attains arbitrarily high precision using only 2m+22m+22m+2 queries, where mmm is the number of modes. To our knowledge, this is the first provably efficient learning algorithm for a multiparameter family of continuous-variable unitaries.
Continuous-variable systems enable key quantum technologies in computation, communication, and sensing. Bosonic Gaussian states emerge naturally in various such applications, including gravitational-wave and dark-matter detection. A fundamental question is how to characterize an unknown bosonic Gaussian state from as few samples as possible. Despite decades-long exploration, the ultimate efficiency limit remains unclear. In this work, we study the necessary and sufficient number of copies to learn an nnn-mode Gaussian state, with energy less than EEE, to ε\varepsilonε trace distance with high probability. We prove a lower bound of Ω(n3/ε2)Ω(n^3/\varepsilon^2)Ω(n3/ε2) for Gaussian measurements, matching the best known upper bound up to doubly-log energy dependence, and Ω(n2/ε2)Ω(n^2/\varepsilon^2)Ω(n2/ε2) for arbitrary measurements. We further show an upper bound of O~(n2/ε2)\widetilde{O}(n^2/\varepsilon^2)O(n2/ε2) given that the Gaussian state is promised to be either pure or passive. Interestingly, while Gaussian measurements suffice for nearly optimal learning of pure Gaussian states, non-Gaussian measurements are provably required for optimal learning of passive Gaussian states. Finally, focusing on learning single-mode Gaussian states via non-entangling Gaussian measurements, we provide a nearly tight bound of Θ~(E/ε2)\widetildeΘ(E/\varepsilon^2)Θ(E/ε2) for any non-adaptive schemes, showing adaptivity is indispensable for nearly energy-independent scaling. As a byproduct, we establish sharp bounds on the trace distance between Gaussian states in terms of the total variation distance between their Wigner distributions, and obtain a nearly tight sample complexity bound for learning the Wigner distribution of any Gaussian state to ε\varepsilonε total variation distance. Our results significantly advance quantum learning theory in the bosonic regimes and have practical impact in quantum sensing and benchmarking applications.