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

Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized $k$-Orthogonal Vectors

Dhruv Prasad Deshpande, Abhishek Mishra

Published Nov 10, 2026• 0 citations
arXivHTMLPDF

Abstract

We study exact evaluation of the arithmetized $k$-Orthogonal Vectors polynomial $FOV^k$ of Ball et al. (2017, 2018). For every fixed integer $k \geq 3$, set $d(n) = \left \lceil \log^2 n \right \rceil$. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant $\varepsilon > 0$, no uniform quantum algorithm runs in $O(n^{k/2 - \varepsilon})$ time on every input and evaluates this polynomial correctly with probability at least $3 / 4$ over a uniformly random input in $\mathbb F_{p(n)}^{knd(n)}$ and the algorithm's internal randomness, for all sufficiently large $n$. This holds when $p(n)$ is the smallest prime greater than $n^{k - 1}$ and when it is the smallest prime greater than $n^k$. Our direct reduction combines classical polynomial self-correction with calls to a quantum average-case evaluator. For the smaller prime, random sampling finds an orthogonal tuple with constant probability whenever the count is large enough to wrap around modulo $p(n)$; otherwise, the exact residue determines the answer. For the larger prime, quantum minimum finding and an asymptotic prime-gap bound account for the cost of generating the prescribed field. In view of prior isolation-based reductions permitting small characteristics, we present these results as explicit reductions for the two canonical-prime families, with all setup costs included in the uniform quantum running time. The hardness guarantee concerns single-instance exact evaluation; a matching quantum evaluation algorithm and a quantum proof-of-work protocol remain open.

DOI
10.48550/arxiv.2611.14411

Related papers

Improved Quantum Random Self-Reduction for Linear Problems

Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu

We study quantum random self-reductions for linear problems over finite fields. Let $M\in\mathbb{F}^{n\times n}$ be an arbitrary matrix, and let $\mathcal{O}$ be an oracle that agrees with the linear map $x\mapsto Mx$ on an $\varepsilon$-fraction of inputs $x\sim\mathbb{F}^n$. Given coherent access to $\mathcal{O}$ and coherent entry access to $M$, we give a uniform quantum reduction that computes $Mx$ on any prescribed input $x$ with probability at least $2/3$ in time $\widetilde{O}(nT^{1/3})$, for $n\le T\le n^{3/2}$ and constant field size and $\varepsilon$, where $T$ is the cost of one coherent query to $\mathcal{O}$. In particular, when $T=\widetilde{O}(n)$, the reduction runs in time $\widetilde{O}(n^{4/3})$, improving the $\widetilde{O}(n^{3/2}+T)$ reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024). Our reduction uses the Bogolyubov--Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov--Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.

quant-pharXiv:2609.39823•Oct 1, 2026•1 citation

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +1 more

The local Hamiltonian (LH) problem is the canonical $\mathsf{QMA}$-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2^{(1-\varepsilon)n})$ for any $\varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time $O(2^{(1-\varepsilon)n/2})$ for any $\varepsilon>0$ under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of $\mathsf{QMA}$ problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in $O(\sqrt{2^n})$ time for an arbitrary $1/\mathrm{poly}(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a $T$-time quantum circuit acting on $N$ qubits into a $(d+1)$-local Hamiltonian acting on $N+O(T^{1/d})$ qubits. This improves the standard construction based on the unary clock, which uses $N+O(T)$ qubits.

quant-pharXiv:2602.14379•Leibniz international proceedings in informatics•Feb 17, 2026•2 citations

Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness

Natansh Mathur, Iordanis Kerenidis

Sampling problems give some of the clearest conditional separations between quantum and classical computation. In Fermion Sampling, passive linear optics acts on a non-Gaussian magic input. Globally Haar-random transformations give anticoncentration and high-precision average-case hardness, but require linear depth and quadratically many gates. A natural open question is whether linear depth is necessary? We show that logarithmic depth suffices for both guarantees in the same ensemble. For fresh uniform matchings with independent Haar two-mode gates, the collision reaches the passive-Haar scale at a sharp threshold of $\log n/\log(9/4)\approx0.855\log_2 n$ layers, with an explicit limiting transition profile and a matching lower bound from two-particle correlations. The mechanism is input-dependent: the magic input suppresses the extensive weight of the slowest relaxation mode, leaving the next to set the scale. An occupation-basis input retains large collision even under full Haar randomness. At a larger logarithmic depth, we prove, in the real-RAM model, average-case $\#\mathsf{P}$-hardness of estimating output probabilities to additive error $2^{-O(n\log^2 n)}$ on any fixed fraction of instances above $3/4$. We construct hard instances in four native layers, embed them in typical schedules, and interpolate along Cayley paths using a rational linear-program decoder. A finite $192$-gate alphabet preserves the collision law exactly. Both guarantees use logarithmic native fermionic depth between arbitrary mode pairs and $O(n\log n)$ gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the $1/N$ scale, where $N=\binom{n}{n/2}$, required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.

quant-pharXiv:2609.40100•Oct 1, 2026•2 citations

Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry

Maximilian J. Kramer, Carsten Schubert, Jens Eisert

For general max-k-XORSAT with $k \geq 3$, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless $\mathsf{P} = \mathsf{NP}$: approximating beyond the random-assignment value of $1/2$ is $\mathsf{NP}$-hard. The picture changes when each variable appears in at most $D$ constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order $1/\sqrt{D}$. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields $\mathbb{F}_q$, proving that it is $\mathsf{NP}$-hard to exceed $r/q + \mathcal{O}_{q,r}(1/\sqrt{D})$. These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on $(k,D)$-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic $1/\sqrt{D \log D}$ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the $1/\sqrt{D}$ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.

quant-pharXiv:2606.13570•Jun 12, 2026•3 citations

Computational Bounds for fff-Routing

Oren Renard, Nicholas Spooner

The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, Physical Review A, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers. Our techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length $n$ and a sufficiently small constant $ε>0$, a uniform strategy running in time $T$ and succeeding with probability at least $1-ε$ on every input implies the following computational bounds on $f$. 1. If the strategies are arbitrary quantum channels, then $f\in \mathrm{QSZK}(\mathrm{poly}(T))$, where $\mathrm{QSZK}(T)$ is the class of languages having quantum statistical zero-knowledge proofs in which the verifier runs in time $T$ and the simulator in time $\mathrm{poly}(T)$. 2. If the strategies are Clifford+T circuits using at most $t$ magic gates, then $f\in \mathrm{DTIME}(\mathrm{poly}(T2^t))$. 3. If the strategies are explicit Pauli-sparse unitaries acting on at most $T$ qubits and having at most $s$ nonzero Pauli coefficients, then $f\in \mathrm{DTIME}(\mathrm{poly}(Ts))$. Time and space hierarchies then yield explicit functions secure against superlinear and even all polynomial-time adversaries under our computational restrictions. These bounds exceed the bounded-storage qubit bound $q\leq\log n$ of Bluhm, Christandl, and Speelman (Nature Physics, 2022) for the inner product function $f=\mathrm{IP}$, at the cost of restricting adversarial computation and increasing honest evaluation complexity.

quant-pharXiv:2609.40278•Oct 1, 2026•0 citations

Exponential improvements to the average-case hardness of BosonSampling

Adam Bouland, Ishaun Datta, Bill Fefferman +1 more

BosonSampling and Random Circuit Sampling are important both as a theoretical tool for separating quantum and classical computation, and as an experimental means of demonstrating quantum speedups. Prior works have shown that average-case hardness of sampling follows from certain unproven conjectures about the hardness of computing output probabilities, such as the Permanent-of-Gaussians Conjecture (PGC), which states that $e^{-n \log n-n-O(\log n)}$ additive-error estimates to the output probability of most random BosonSampling experiments are #P-hard. Prior works have only shown weaker average-case hardness results that do not imply sampling hardness. Proving these conjectures has become a central question in quantum complexity. In this work, we show that $e^{-n \log n-n-O\left(n^{\delta}\right)}$ additive-error estimates to output probabilities of most random BosonSampling experiments are #P-hard for any $\delta\gt 0$, exponentially improving on prior work. In the process, we circumvent all known barrier results for proving PGC. The remaining hurdle to prove PGC is now “merely” to show that the $O\left(n^{\delta}\right)$ in the exponent can be improved to $O(\log n)$. We also obtain an analogous result for Random Circuit Sampling. We then show, for the first time, a hardness of average-case classical sampling result for BosonSampling, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-2^{-\tilde{O}\left(N^{1 / 3}\right)}$ for input size N, unless the Polynomial Hierarchy collapses. This exponentially improves upon the state-of-the-art. To do this, we introduce new proof techniques which tolerate exponential loss in the worst-to-average-case reduction. This opens the possibility to show the hardness of average-case sampling without ever proving PGC.

arXiv:2411.04566•Annual Symposium on Foundations of Computer Science•Dec 14, 2025•11 citations
Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized kkk-Orthogonal Vectors
We study exact evaluation of the arithmetized kkk-Orthogonal Vectors polynomial FOVkFOV^kFOVk of Ball et al. (2017, 2018). For every fixed integer k≥3k \geq 3k≥3, set d(n)=⌈log⁡2n⌉d(n) = \left \lceil \log^2 n \right \rceild(n)=⌈log2n⌉. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant ε>0\varepsilon > 0ε>0, no uniform quantum algorithm runs in O(nk/2−ε)O(n^{k/2 - \varepsilon})O(nk/2−ε) time on every input and evaluates this polynomial correctly with probability at least 3/43 / 43/4 over a uniformly random input in Fp(n)knd(n)\mathbb F_{p(n)}^{knd(n)}Fp(n)knd(n)​ and the algorithm's internal randomness, for all sufficiently large nnn. This holds when p(n)p(n)p(n) is the smallest prime greater than nk−1n^{k - 1}nk−1 and when it is the smallest prime greater than nkn^knk. Our direct reduction combines classical polynomial self-correction with calls to a quantum average-case evaluator. For the smaller prime, random sampling finds an orthogonal tuple with constant probability whenever the count is large enough to wrap around modulo p(n)p(n)p(n); otherwise, the exact residue determines the answer. For the larger prime, quantum minimum finding and an asymptotic prime-gap bound account for the cost of generating the prescribed field. In view of prior isolation-based reductions permitting small characteristics, we present these results as explicit reductions for the two canonical-prime families, with all setup costs included in the uniform quantum running time. The hardness guarantee concerns single-instance exact evaluation; a matching quantum evaluation algorithm and a quantum proof-of-work protocol remain open.
We study quantum random self-reductions for linear problems over finite fields. Let M∈Fn×nM\in\mathbb{F}^{n\times n}M∈Fn×n be an arbitrary matrix, and let O\mathcal{O}O be an oracle that agrees with the linear map x↦Mxx\mapsto Mxx↦Mx on an ε\varepsilonε-fraction of inputs x∼Fnx\sim\mathbb{F}^nx∼Fn. Given coherent access to O\mathcal{O}O and coherent entry access to MMM, we give a uniform quantum reduction that computes MxMxMx on any prescribed input xxx with probability at least 2/32/32/3 in time O~(nT1/3)\widetilde{O}(nT^{1/3})O(nT1/3), for n≤T≤n3/2n\le T\le n^{3/2}n≤T≤n3/2 and constant field size and ε\varepsilonε, where TTT is the cost of one coherent query to O\mathcal{O}O. In particular, when T=O~(n)T=\widetilde{O}(n)T=O(n), the reduction runs in time O~(n4/3)\widetilde{O}(n^{4/3})O(n4/3), improving the O~(n3/2+T)\widetilde{O}(n^{3/2}+T)O(n3/2+T) reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024). Our reduction uses the Bogolyubov--Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov--Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.
The local Hamiltonian (LH) problem is the canonical QMA\mathsf{QMA}QMA-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on nnn qubits cannot be solved classically in time O(2(1−ε)n)O(2^{(1-\varepsilon)n})O(2(1−ε)n) for any ε>0\varepsilon>0ε>0 under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time O(2(1−ε)n/2)O(2^{(1-\varepsilon)n/2})O(2(1−ε)n/2) for any ε>0\varepsilon>0ε>0 under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of QMA\mathsf{QMA}QMA problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in O(2n)O(\sqrt{2^n})O(2n​) time for an arbitrary 1/poly(n)1/\mathrm{poly}(n)1/poly(n) relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a TTT-time quantum circuit acting on NNN qubits into a (d+1)(d+1)(d+1)-local Hamiltonian acting on N+O(T1/d)N+O(T^{1/d})N+O(T1/d) qubits. This improves the standard construction based on the unary clock, which uses N+O(T)N+O(T)N+O(T) qubits.
Sampling problems give some of the clearest conditional separations between quantum and classical computation. In Fermion Sampling, passive linear optics acts on a non-Gaussian magic input. Globally Haar-random transformations give anticoncentration and high-precision average-case hardness, but require linear depth and quadratically many gates. A natural open question is whether linear depth is necessary? We show that logarithmic depth suffices for both guarantees in the same ensemble. For fresh uniform matchings with independent Haar two-mode gates, the collision reaches the passive-Haar scale at a sharp threshold of log⁡n/log⁡(9/4)≈0.855log⁡2n\log n/\log(9/4)\approx0.855\log_2 nlogn/log(9/4)≈0.855log2​n layers, with an explicit limiting transition profile and a matching lower bound from two-particle correlations. The mechanism is input-dependent: the magic input suppresses the extensive weight of the slowest relaxation mode, leaving the next to set the scale. An occupation-basis input retains large collision even under full Haar randomness. At a larger logarithmic depth, we prove, in the real-RAM model, average-case #P\#\mathsf{P}#P-hardness of estimating output probabilities to additive error 2−O(nlog⁡2n)2^{-O(n\log^2 n)}2−O(nlog2n) on any fixed fraction of instances above 3/43/43/4. We construct hard instances in four native layers, embed them in typical schedules, and interpolate along Cayley paths using a rational linear-program decoder. A finite 192192192-gate alphabet preserves the collision law exactly. Both guarantees use logarithmic native fermionic depth between arbitrary mode pairs and O(nlog⁡n)O(n\log n)O(nlogn) gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the 1/N1/N1/N scale, where N=(nn/2)N=\binom{n}{n/2}N=(n/2n​), required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.
For general max-k-XORSAT with k≥3k \geq 3k≥3, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless P=NP\mathsf{P} = \mathsf{NP}P=NP: approximating beyond the random-assignment value of 1/21/21/2 is NP\mathsf{NP}NP-hard. The picture changes when each variable appears in at most DDD constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order 1/D1/\sqrt{D}1/D​. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-Ekkk-LINSAT(q,r)(q,r)(q,r) with bounded degree DDD and over arbitrary finite fields Fq\mathbb{F}_qFq​, proving that it is NP\mathsf{NP}NP-hard to exceed r/q+Oq,r(1/D)r/q + \mathcal{O}_{q,r}(1/\sqrt{D})r/q+Oq,r​(1/D​). These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on (k,D)(k,D)(k,D)-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic 1/Dlog⁡D1/\sqrt{D \log D}1/DlogD​ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the 1/D1/\sqrt{D}1/D​ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.
The fff-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, Physical Review A, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers. Our techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length nnn and a sufficiently small constant ε>0ε>0ε>0, a uniform strategy running in time TTT and succeeding with probability at least 1−ε1-ε1−ε on every input implies the following computational bounds on fff. 1. If the strategies are arbitrary quantum channels, then f∈QSZK(poly(T))f\in \mathrm{QSZK}(\mathrm{poly}(T))f∈QSZK(poly(T)), where QSZK(T)\mathrm{QSZK}(T)QSZK(T) is the class of languages having quantum statistical zero-knowledge proofs in which the verifier runs in time TTT and the simulator in time poly(T)\mathrm{poly}(T)poly(T). 2. If the strategies are Clifford+T circuits using at most ttt magic gates, then f∈DTIME(poly(T2t))f\in \mathrm{DTIME}(\mathrm{poly}(T2^t))f∈DTIME(poly(T2t)). 3. If the strategies are explicit Pauli-sparse unitaries acting on at most TTT qubits and having at most sss nonzero Pauli coefficients, then f∈DTIME(poly(Ts))f\in \mathrm{DTIME}(\mathrm{poly}(Ts))f∈DTIME(poly(Ts)). Time and space hierarchies then yield explicit functions secure against superlinear and even all polynomial-time adversaries under our computational restrictions. These bounds exceed the bounded-storage qubit bound q≤log⁡nq\leq\log nq≤logn of Bluhm, Christandl, and Speelman (Nature Physics, 2022) for the inner product function f=IPf=\mathrm{IP}f=IP, at the cost of restricting adversarial computation and increasing honest evaluation complexity.
BosonSampling and Random Circuit Sampling are important both as a theoretical tool for separating quantum and classical computation, and as an experimental means of demonstrating quantum speedups. Prior works have shown that average-case hardness of sampling follows from certain unproven conjectures about the hardness of computing output probabilities, such as the Permanent-of-Gaussians Conjecture (PGC), which states that e−nlog⁡n−n−O(log⁡n)e^{-n \log n-n-O(\log n)}e−nlogn−n−O(logn) additive-error estimates to the output probability of most random BosonSampling experiments are #P-hard. Prior works have only shown weaker average-case hardness results that do not imply sampling hardness. Proving these conjectures has become a central question in quantum complexity. In this work, we show that e−nlog⁡n−n−O(nδ)e^{-n \log n-n-O\left(n^{\delta}\right)}e−nlogn−n−O(nδ) additive-error estimates to output probabilities of most random BosonSampling experiments are #P-hard for any δ>0\delta\gt 0δ>0, exponentially improving on prior work. In the process, we circumvent all known barrier results for proving PGC. The remaining hurdle to prove PGC is now “merely” to show that the O(nδ)O\left(n^{\delta}\right)O(nδ) in the exponent can be improved to O(log⁡n)O(\log n)O(logn). We also obtain an analogous result for Random Circuit Sampling. We then show, for the first time, a hardness of average-case classical sampling result for BosonSampling, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability 1−2−O~(N1/3)1-2^{-\tilde{O}\left(N^{1 / 3}\right)}1−2−O~(N1/3) for input size N, unless the Polynomial Hierarchy collapses. This exponentially improves upon the state-of-the-art. To do this, we introduce new proof techniques which tolerate exponential loss in the worst-to-average-case reduction. This opens the possibility to show the hardness of average-case sampling without ever proving PGC.