Toward Quantum Advantage in Learning Parities with Structured Noise via Lower Bound Optimization of the Condition Number

Toward Quantum Advantage in Learning Parities with Structured Noise via Lower Bound Optimization of the Condition Number∗ Yusen Han,1, † Xuelian Li,1, ‡ Juntao Gao,2, § and Bo Song3, ¶ 1

School of Mathematics and Statistics, Xidian University, Xi’an, China School of Telecommunications and Engineering, Xidian University, Xi’an, China 3 China Telecom Quantum Information Technology Group Co., Ltd, Hefei, China

arXiv:2608.19122v1 [cs.CR] 19 Aug 2026

2

Learning Parities with Structured Noise (LPSN) can be reduced to solving nonlinear Boolean systems. In quantum computing, such systems are typically transformed into Macaulay linear systems and solved via quantum linear system algorithms, a process severely limited by the condition number. To address this, we propose a novel reduction method for Macaulay linear systems. Under the assumptions of Ding et al., we derive a condition number lower bound incorporating a scaling factor. This reduction not only guarantees efficient quantum state preparation but also exhibits a distinct advantage regarding the condition number interval relative to the reduced right-hand side vector, thereby reducing the lower bound of the condition number and ultimately optimizing the upper bound on the time complexity of the quantum algorithm for solving Boolean systems. Furthermore, applying this improved quantum algorithm to LPSN significantly reduces sample complexity by exploiting the Macaulay system’s solution structure. We further provide a concrete logical-level quantum resource estimate, demonstrating that the optimized condition number translates directly into a reduction in circuit width, depth, and gate count. Finally, we establish an algorithm selection strategy by systematically comparing quantum and classical approaches across noise pattern adaptability, sample complexity, and time complexity. Results demonstrate that our quantum algorithm exhibits the potential to outperform classical counterparts under specific parameter regimes. Keywords: LPSN, Macaulay linear systems, condition number lower bound, reduction, complexity.

I.

INTRODUCTION

The Learning Parities with Noise (LPN) problem is a core hardness assumption in computational learning and cryptography. Standard LPN requires recovering a secret vector s from samples (a, a · s ⊕ η). Despite providing post-quantum security for numerous cryptographic systems [1–5], the cumbersome error-correction necessitated by purely random noise severely limits practical efficiency. This paper focuses on the Learning Parities with Structured Noise (LPSN) problem introduced by Arora and Ge [6]. Its core innovation lies in constraining the noise vector η with a polynomial P such that P (η) = 0. Given oracle samples (AT , AT s ⊕ η), this polynomial structure significantly improves mathematical tractability while preserving security, offering a novel pathway for efficient cryptographic protocol design. Previous Work. Existing algorithms for the LPN problem face efficiency bottlenecks. In the high-noise regime, Blum et al. [7] proposed the state-of-the-art algorithm n with O(2Θ( log2 n ) ) complexity. In the low-noise regime, mainstream Gaussian elimination methods require approximately O(enp ) time. Consequently, practical cryptographic designs [8–10] generally assume √ LPN remains secure when the noise rate is below 1/ n. ∗ A footnote to the article title † yusenhan01@163.com

‡ xlli@mail.xidian.edu.cn

§ jtgao@mail.xidian.edu.cn

¶ songbo1@chinatelecom.cn

Quantum computing provides a new perspective. Inspired by Blum et al. [7], Esser et al. [11] proposed a hybrid quantum attack, subsequently optimized by Jiao [12]. In Information Set Decoding approaches, Bernstein [13] improved the complexity of the classical Prange [14] and May-Ozerov [15] algorithms; the current optimal exponent derives from the quantum random walk algorithm by Kachigar and Tillich [16]. Additionally, Tran and Vaudenay [17] combined Gaussian elimination with Grover’s search, achieving non-asymptotic advantages in largedimension, low-noise scenarios. Regarding the LPSN problem, Arora and Ge [6], building on linearization techniques from [18], proposed classical polynomial-time recovery algorithms, provided that sufficient samples are available and the number of correlated noises is constant. Because the LPSN problem does not necessitate a vector sparsity assumption, its solving algorithms exhibit broad applicability. However, classical efficiency has reached its limits. Exploring the hardness of LPSN under small sample sizes and its potential for quantum acceleration has thus become a critical open problem. The algebraic approach to the LPSN problem requires processing large-scale Boolean systems, for which quantum linear system algorithms (QLSA) offer a breakthrough. Following the foundational HHL algorithm [19] featuring logarithmic complexity, this field has advanced rapidly: Ambainis [20] introduced variable-time amplitude amplification to reduce condition number dependence to linear; Berry et al. [21] utilized Hamiltonian simulation via truncated Taylor series to lower sparsity dependence to linear; Childs et al. [22] achieved an exponential improvement in precision dependence. For dense matrices,

2 Wossnig et al. [23] bypassed sparsity constraints using quantum random access memory, while Chakraborty et al. [24] exponentially enhanced precision by integrating block-encoding with variable-time amplitude estimation. Furthermore, Lin et al. [25] achieved near-optimal query complexity for sparse matrices, and Nghiem [26] recently eliminated the direct dependence on the condition number. Beyond asymptotic complexity, the practical feasibility of QLSA-based algorithms is ultimately dictated by their concrete physical resource requirements. Scherer et al. [27] presented the first concrete logical-level resource estimate for the HHL algorithm, taking the computation of the electromagnetic scattering cross section of a 2D target as a benchmark. Their analysis shows that, even in the idealized logical-circuit model, the algorithm demands several hundred logical qubits together with a gate count and circuit depth exceeding the order of 1025 ; crucially, these resources are dominated by the Hamiltonian simulation and depend critically on the condition number κ and the target precision ε, while scaling only logarithmically with the matrix size. This indicates that the condition number, rather than the problem size itself, fundamentally governs the resource cost of QLSA-based algorithms. Chen and Gao [28] pioneered a quantum algorithm for solving nonlinear Boolean systems by transforming them into complex Macaulay linear systems, where the solving efficiency heavily relies on the matrix condition number, the magnitude of which remains difficult to evaluate. To quantitatively evaluate the condition number, Ding et al. [29] proposed a reduction method, proving that for a system comprising n Boolean variables, assuming its solution has a Hamming weight of h, the condition number lower bound
for a reduced Macaulay matrix of 1 degree D is Ω(( D+h − 1) 2 ). When h = Θ(n), the exh ponential growth of the condition number renders this algorithm inferior to Grover’s search. To address this, they introduced the Boolean Macaulay linear system to re1 duce the lower bound to Ω((2h − 1) 2 ). This improvement ensures that the condition number remains polynomial when h = O(log2 n), thereby retaining the potential for super-polynomial quantum speedup. Our Contributions. This paper makes multidimensional contributions to solving the LPSN problem. By integrating the binary Schwartz-Zippel lemma with inequality bounding techniques, we derive the exact sample and time complexities required for the classical bit-by-bit guessing and algebraic Gaussian elimination algorithms to achieve a success probability of 1 − ε, thereby explicitly delineating their theoretical boundaries. To reduce the lower bound of the condition number in Chen and Gao’s quantum algorithm [28], we propose a novel polynomial system reduction method. For a nonlinear Boolean system F comprising r equations and n variables, featuring a sparsity of TF and a unique solution of Hamming weight h, this method transforms it into an equivalent 3-sparse complex polynomial system

where all constant terms are strictly −1. This operation ensures the Macaulay matrix strictly satisfies the prerequisites for efficient quantum state preparation within O(TF − 2r) time. Bridging the theoretical gap left by Ding et al. [29] regarding unquantified reduction impacts, we optimize the condition number lower bound
for 1a Macaulay matrix of total degree D from Ω(( D+h − 1) 2 ) h
1 − 21 D+h 2 to Ω((TF − 2r) ( h − 1) ). This reduction framework naturally extends to Boolean Macaulay linear systems, further decreasing the condition 1 −1 number lower bound to Ω(TF 2 (2h − 1) 2 ). Furthermore, we empirically validate these tighter bounds by constructing numerical matrix instances that breach the theoretical limits established by Ding et al. using an iterative optimization algorithm. Building on the resource-estimation perspective of Scherer et al. [27], we further carry out a fine-grained logical-level resource analysis of the proposed Macaulay and Boolean-Macaulay quantum algorithms. We derive explicit closed-form expressions for the circuit width, depth, and gate count, and show that, since the circuit size scales as the square of the condition number, the condition-number optimization achieved by our reduction translates directly into a reduction in circuit depth and gate count. This establishes that our improvement is not merely asymptotic but yields concrete, quantifiable resource savings. Ultimately, applying the improved quantum algorithm to the LPSN problem achieves an exponential reduction in sample complexity. By comparing time complexities, we provide a comprehensive algorithm selection strategy. Assisted by 3D time complexity surface plots, we reveal √ that even when h = Θ( n), the quantum algorithm possesses the potential to outperform classical algorithms, this further highlighting its theoretical supremacy within specific parameter regimes. Structure of the Paper. The remainder of this paper is organized as follows. Section II introduces the condition number of a matrix, the linearization technique utilized in classical algebraic attacks, as well as the complex-field transformation of Boolean equation systems and the construction of linear systems within the framework of quantum algebraic attacks. Section III formalizes the LPN and LPSN problems based on the oracle model. Section IV provides a quantitative analysis of classical algorithms, deriving their sample and time complexities under a specified success probability. Section V details the improved quantum algorithm for solving Boolean systems and evaluates its resource requirements when applied to the LPSN problem. Section VI provides a concrete evaluation of the quantum resources required by the proposed algorithms. Section VII experimentally validates the correctness of the theoretical analysis and proposes algorithm selection strategies tailored to different parameter regimes based on the comparative results. Finally, Section VIII summarizes the content of this paper.

3 II.

PRELIMINARIES

A.

Condition Number

The standard condition number of a matrix A, defined as κ(A) = ∥A∥2 · ∥A+ ∥2 , reflects the global worst-case sensitivity of a linear system. Hereafter, we uniformly utilize ∥A∥ to denote the spectral norm. The condition number with respect to a specific vector b is defined as + κb (A) = ∥A∥ · ∥A∥b∥b∥ . Because b does not necessarily align with the left singular vector corresponding to the minimum singular value, the inequality κb (A) ≤ κ(A) generally holds. This metric provides a tighter error bound and correlates directly with the practical runtime of quantum algorithms. The truncated condition number κk (A) exclusively measures the ratio involving the top k largest singular values. Truncated quantum algorithms attempt to bypass ill-conditioned spectra by operating exclusively within a well-conditioned subspace S defined by singular values c bounded below by κb (A) for c > 1. However, the projection of the solution vector x onto S strictly satisfies ∥ΠS x∥ ≤ κb (A)∥b∥ . This implies that the principal comc ponents of the solution predominantly reside outside this well-conditioned subspace, or the system remains acutely sensitive to perturbations due to a diminished overall norm. Consequently, to accurately capture the solution, truncated algorithms must lower their truncation thresholds, fundamentally failing to evade the complexity bottleneck dictated by κb (A). Because the global bound κ(A) cannot accurately assess the runtime of truncated variants, our subsequent analysis focuses exclusively on κb (A). This metric establishes a rigorous theoretical foundation for evaluating the ultimate performance limits of all QLSA and their truncated variants.

B.

Linearization Techniques in Classical Algebraic Attacks

In the randomized LPSN setting, an attacker treats x ∈ GF(2)n as a variable vector and queries the oracle Q1 to obtain m samples, denoted as (aT1 , b1 )T , . . . , (aTm , bm )T . Given the noise correlation polynomial P (η) = 0, substituting ηi = ai · x ⊕ bi yields a degree-d polynomial constraint over x. Arora and Ge applied straightforward Q linearization by replacing each monomial i∈S xi , where S ⊆ [n] and |S| ≤ d, with a new variable yS . This converts the polynomial into a linear
constraint over a new vector Pd y comprising N = i=1 ni variables, where y∅ = 1 is treated as a P constant: L(P (a1 · x ⊕ b1 , a2 · x ⊕ b2 , . . . , am · x ⊕ bm )) = S⊆[n],|S|≤d cS yS = 0. The linear Boolean system generated through repeated queries consistently admits a valid solution originating Q from the true secret vector s and satisfying yS = i∈S si . Arora and Ge demonstrated that, given ample samples,

the components of this solution corresponding to the original variables match s with high probability. Under the adversarial noise setting involving the oracle Q2 , the attacker constructs a multilinear polynomial R(η) over GF(2) such that R(η) = 0 holds if and only if η decomposes as the sum η = α ⊕ β of two components satisfying P (α) = P (β) = 0. After injecting an auxiliary noise vector β satisfying P (β) = 0 into the oracle samples, the combined noise incorporating the oracle noise α naturally satisfies R(α ⊕ β) = 0. Applying the identical linearization technique yields a linear constraint over the variable vector y: L(R(a1 · x ⊕ b1 ⊕ β1 , a2 · x ⊕ b2 ⊕ β2 , . . . , am · x ⊕ bm ⊕ βm )) = 0. The degree d′ of the polynomial R satisfies 1 ≤ d′ ≤ m and is strictly determined by the algebraic structure of ′ P
redefines the number of new variables to N = P.d′This n i=1 i . By systematically acquiring ample samples, the attacker constructs a linearized Boolean system containing the genuine solution to successfully extract the secret vector.

C.

Framework of Quantum Algebraic Attacks 1.

Representation of Boolean Systems over the Complex Field

To apply the HHL algorithm, the Boolean system F over F2 must be transformed into an equivalent system over the complex field C. The mapping C(fi ) = Q⌊ti /2⌋ k=fi (0) (fi − 2k) formulated in [28] ensures that the Boolean solution set over C, denoted as VB (C(F)), is strictly equivalent to the original solution set VF2 (F). Because the number of terms in C(fi ) grows exponentially with the original term count ti and the complexity of the HHL algorithm is highly dependent on matrix sparsity, sparsifying the original system is indispensable. By introducing auxiliary variables Uf , each polynomial fi is decomposed into an s-sparse system S(f, s) satisfying s ≥ 3. Literature [28] proves the algebraic equivalence of this decomposition. The derived equivalent complex system P (F, s) = C(S(F, s)) strictly satisfies the projection relationship VF2 (F) = ProjX VB (P (F, s)) while effectively bounding the growth of the total number of variables and equations. In practice, we typically set b ) des = 3. Furthermore, the optimized mapping C(f fined by exploiting the idempotent properties of Boolean variables yields a practical number of terms substantially lower than the theoretical bound.

2.

Macaulay Linear Systems

For a complex polynomial system F = {f1 , . . . , fr } ⊂ C[X], let the variable set X = {x1 , . . . , xn } be lexicographically ordered, and define md as the ordered set of all monomials dividing xd1 · · · xdn with a cardinality of

4 (d+1)n . To normalize the system, we assume the constant terms of the first ρ polynomials are −1 while the remainder are 0. We select a target degree D ≥ maxi deg(fi ) and determine the smallest integers d¯ and D̄ satisfying d¯ ≥ D − mini deg(fi ) and D̄ ≥ D such that d¯ + 1 = 2δ and D̄ + 1 = 2∆ hold for δ, ∆ ∈ N. Multiplying each fi by monomials md,j ¯ ∈ md¯ satisfying deg(md,j ¯ ) ≤ D−deg(fi ) transforms the equations into the matrix form MF ,D mD = bF ,D . Herein, the Macaulay matrix MF ,D has dimensions r2nδ × (2n∆ − 1), the column vector mD contains all monomials in mD̄ \ {1}, and the right-hand side vector bF ,D consists of the negated constant terms −fi (0).

3.

Boolean Macaulay Linear Systems

Qn Qn min{1,ai } Define the mapping φ ( i=1 xai i ) = i=1 xi , which is linearly extended to C[X] to convert complex polynomials into multilinear polynomials. For a polynomial system F = {f1 , . . . , fr } ⊆ C[X], its degree-d (d ≤ n) Boolean Macaulay matrix BF ,d is generated by polynomials φ(mfi ), where m is a multilinear monomial satisfying deg(φ(mfi )) ≤ d. The columns of BF ,d are indexed by all multilinear monomials of degree at most d under a specified ordering. The matrix entry at row mfi and column m′ is precisely the coefficient of m′ in φ(mfi ). Let md be the column vector of all such non-constant multilinear monomials, and bF ,d be the column vector comprising the negated constant terms of φ(mfi ). This establishes the degree-d Boolean Macaulay linear system: BF ,d md = bF ,d . Since
Pd an n-variable set generates a maximum of i=0 ni multilinear monomials of degree at most d, the dimensions of 
Pd
Pd n BF ,d are strictly bounded to r i=0 ni × − 1 . i=0 i

III.

PROBABILISTIC FORMALIZATION OF THE LEARNING PARITIES WITH STRUCTURED NOISE PROBLEM

Definition III.1 (LPN Oracle). Let the secret vector s ∈ Zn2 be chosen uniformly at random, and let p ∈ (0, 1) denote the noise rate characterizing the Bernoulli distribution Ber(p). The LPN oracle Q(n, p, s) outputs independent random samples ψ = (aT , b) ∈ Zn+1 according 2 to the distribution Q(n, p, s), defined as follows: 

Ber( 1 )

Ber(p)

2 ψ = (aT , b) | a ←−−− − Zn2 , η ←−−−− Z2 ,  n s ∈ Z2 , b = ⟨a, s⟩ ⊕ η .

Given the parameters n and p, the attacker’s objective is to recover the secret vector s by repeatedly querying this oracle.

Definition III.2 (k-LPN Oracle). Under identical parameter settings, a single query to the k-LPN oracle Q(n, k, p, s) is strictly equivalent to k independent queries to the standard LPN oracle. It outputs samples ψ ′ = (AT , b) according to the distribution Q(n, k, p, s), defined as:  Ber( 21 ) ψ ′ = (AT , b) | ∀1 ≤ i ≤ k, ai ←−−− − Zn2 , Ber(p)

ηi ←−−−− Z2 , s ∈ Zn2 , A = (a1 , a2 , . . . , ak ),  T T η = (η1 , η2 , . . . , ηk ) , b = A s ⊕ η . Specifically, the oracle generates a random matrix An×k and a noise vector η ∈ Zk2 to compute b = AT s ⊕ η. The attacker, aware of n, k, and p, aims to recover s from these outputs. Building upon this theoretical foundation, we subsequently introduce the LPSN oracle to formalize the correlations among the sample noise components. Definition III.3 (Randomized LPSN Oracle). Let the secret vector s ∈ Zn2 be chosen uniformly at random. Given an m-variable, non-zero multilinear polynomial P (η) of degree d, let µ be an arbitrary distribution over all valid noise patterns satisfying P (η) = 0. The randomized LPSN oracle Q1 (n, m, P, µ, s) outputs independent samples ψ1 = (AT , b) according to the distribution Q1 , defined as follows:  ψ1 = ((aT1 , b1 )T , (aT2 , b2 )T , . . . , (aTm , bm )T )T = Ber( 1 )

µ

2 n − Zn2 , η ← − Zm (AT , b) | ∀1 ≤ i ≤ m, ai ←−−− 2 , s ∈ Z2 ,

A = (a1 , a2 , . . . , am ), µ ∈ {D ∈ P(Zm 2 )|  supp(D) = {η | P (η) = 0}}, b = AT s ⊕ η . In this model, the oracle uniformly samples the matrix An×m and independently samples the noise vector η ∼ µ (i.e., it cannot observe A when selecting η), outputting b = AT s ⊕ η. The attacker, aware of n, m, and P but ignorant of the specific distribution µ, aims to recover s through oracle queries. Definition III.4 (Adversarial LPSN Oracle). Under identical parameter settings, the adversarial LPSN oracle Q2 (n, m, P, µ, s) allows for adaptive noise selection. It outputs samples ψ2 = (AT , b) according to the distribution Q2 , defined as:  ψ2 = ((aT1 , b1 )T , (aT2 , b2 )T , . . . , (aTm , bm )T )T = Ber( 1 )

µ,a1 ,a2 ,...,am

2 (AT , b) | ∀1 ≤ i ≤ m, ai ←−−− − Zn2 , η ←−−−−−−−−− Zm 2 ,

s ∈ Zn2 , A = (a1 , a2 , . . . , am ), µ ∈ {D ∈ P(Zm 2 )|  supp(D) = {η | P (η) = 0}}, b = AT s ⊕ η .

5 The fundamental distinction from the randomized model is that Q2 adaptively selects the valid noise vector η ∼ µ based on the already generated matrix A. Feldman demonstrated that a T -time algorithm for the randomized LPN problem implies a T 3 -time algorithm for the adversarial variant [30]. However, since Arora and Ge have established polynomial-time algorithms for LPSN, we directly evaluate specific algorithms based on their polynomial degrees under distinct noise patterns, rather than employing this generic reduction. Furthermore, the correlation polynomial P must satisfy a specific algebraic condition: there must exist at least one ρ ∈ GF(2)m such that ρ = ̸ η ⊕ η ′ for all valid noise pairs ′ satisfying P (η) = P (η ) = 0. Arora and Ge proved that violating this condition empowers an adaptive oracle to perfectly deceive any learning algorithm [6]. Consequently, imposing this algebraic condition is both necessary and practically reasonable.

Theorem IV.2. Given (N + log2 1ε )2d samples from the oracle Q1 (n, m, P, µ, s), the time complexity of Algorithm 1 is strictly bounded by O((nd + log2 1ε )2d n2d+1 ).

B. Complexity Evaluation of the Algebraic Algorithm Based on Gaussian Elimination

A primary limitation of the B-BG algorithm is its strict requirement for independence between the noise vector η and the uniformly random vectors ai . To address this, we introduce an algebraic algorithm based on Gaussian elimination (A-GE), which is applicable to adversarial structured noise patterns under specific algebraic conditions.

1. IV. REFINED COMPLEXITY CHARACTERIZATION OF ALGEBRAIC ATTACKS ON THE LPSN PROBLEM

Existing work [6] provides only rough asymptotic estimates for classical algebraic attacks. This section strictly establishes their time complexity upper bounds by explicitly determining the sample complexity required to guarantee a specific success probability of 1 − ε.

A.

Precise Complexity Analysis of the Bit-by-Bit Guessing Algorithm

We first evaluate the Bit-by-Bit guessing (B-BG) algorithm. The following theorems delineate its sample and time complexities for a given success probability. Algorithm 1 B-BG Require: {(AT , b)}M , P (η). Ensure: x ∈ Zn 2. 1: for j = 1 to n do 2: for l = 1 to M do 3: for i = 1 to m do ) Ber( 1 2

4: âi,j ←−−−− Z2 5: âi ← (ai,1 , . . . , âi,j , . . . , ai,n ) 6: Ll (P (â1 · x ⊕ b1 , â2 · x ⊕ b2 , . . . , âm · x ⊕ bm )) = 0 7: L ← {Lk = 0 | 1 ≤ k ≤ M } 8: if Sol(L) = ∅ then 9: xj ← 1 10: else 11: xj ← 0 12: return x = (x1 , x2 , . . . , xn )

Theorem IV.1. By making exactly (N +log2 1ε )2d queries to the oracle Q1 (n, m, P, µ, s), Algorithm 1 recovers the secret vector with probability at least 1 − ε.

Randomized Structured Noise Patterns

The following theorems establish the requisite complexities for a fixed success probability under randomized noise. Algorithm 2 A-GE ′

Require: {(AT , b)}M , P (η). Ensure: x ∈ Zn 2. 1: for l = 1 to M ′ do 2: Ll (P (a1 · x ⊕ b1 , a2 · x ⊕ b2 , . . . , am · x ⊕ bm )) = 0 3: L ← {Lk = 0 | 1 ≤ k ≤ M ′ } 4: x ← Sol(L) 5: return x = (x1 , x2 , . . . , xn )

Theorem IV.3. By making exactly (N + log2 1ε )2m+d queries to the oracle Q1 (n, m, P, µ, s), Algorithm 2 recovers the secret vector with probability at least 1 − ε. Theorem IV.4. Given (N + log2 1ε )2m+d samples from the oracle Q1 (n, m, P, µ, s), the time complexity of Algorithm 2 is strictly bounded by O((nd + log2 1ε )2m+d n2d ).

2.

Adversarial Structured Noise Patterns

Under the adversarial noise setting, the attacker can substitute the correlation polynomial P with a constructed polynomial R to solve the resulting linear system via Algorithm 2. The complexities for achieving a specified success probability are outlined below. ′

Theorem IV.5. By making exactly (N ′ + log2 1ε )2d queries to the oracle Q2 (n, m, P, µ, s), Algorithm 2 recovers the secret vector with probability at least 1 − ε. ′

Theorem IV.6. Given (N ′ + log2 1ε )2d samples from the oracle Q2 (n, m, P, µ, s), the time complexity of Algorithm ′ ′ ′ 2 is strictly bounded by O((nd + log2 1ε )2m+d n2d ).

6 V. COMPLEXITY BOUNDS OF REDUCTION-OPTIMIZED QUANTUM ALGEBRAIC ATTACKS ON THE LPSN PROBLEM

In this section, we propose a novel reduction method to optimize the quantum algorithm for solving Boolean systems, and subsequently apply it to the LPSN problem.

A.

Sample Complexity for Quantum Algebraic Systems

For solving non-linear Boolean systems, we employ the methodology from Section II C 1. By introducing auxiliary variables, the system is transformed into an equivalent 3-sparse Boolean system, and subsequently into a 6-sparse complex-field system. Field equations are appended to ensure strict equivalence between the complex-field solution set and the original Boolean solution set. Finally, the quantum algorithm evaluates the corresponding Macaulay linear system. Theorem V.1. Suppose the oracle Q2 (n, m, P, µ, s) uniformly selects a secret vector s ∈ GF(2)n and vectors ai ∈ GF(2)n , and adaptively samples a noise vector η ∼ µ satisfying P (η) = 0, where P (η) is a degree-d non-linear polynomial satisfying the requisite algebraic condition. Given bi = ai · s ⊕ ηi , we construct non-linear Boolean equations over x: P (a1 · x ⊕ b1 , . . . , am · x ⊕ bm ) = 0. When the number of equations reaches ⌈2m ln 1ε ⌉, this system admits a unique solution x = s with a probability of at least 1 − ε. Proof. Clearly, x = s is a valid solution. Assume another solution s′ = ̸ s exists, defining a non-zero difference vector v = s′ ⊕ s. Since s′ satisfies the equations, we have ai · s′ ⊕ bi = ai · v ⊕ ηi . Let δi = ai · v; thus, P (δ ⊕ η) = 0 holds. Because both η and δ ⊕ η are valid noise patterns, the algebraic condition (η ⊕ η ′ ̸= ρ) necessitates that δ ̸= ρ. Although η is chosen adaptively, this occurs after the random selection of ai . Since δ depends strictly on ai and the fixed v, it is completely determined. Given uniformly random ai and v ̸= 0, δ is uniformly distributed in GF(2)m . The probability that δ = ρ for a single sample is 21m . For T equations, the probability that all samples satisfy δ = ̸ ρ is (1 − 21m )T . Setting (1 − 21m )T ≤ ε and applying ln(1 − p) < −p yields T ≥ ⌈2m ln 1ε ⌉. Thus, with this sample size, the system admits a unique solution with a probability of at least 1 − ε. In classical algebraic attacks, direct linearization cannot guarantee that the solution of the linear system satisfies the inherent non-linear constraints, necessitating massive samples to probabilistically isolate the secret vector’s components. Conversely, as established in Section II C 2, the quantum algorithm leverages the solution structure of the Macaulay linear system to successfully recover the

secret vector simply by ensuring the unique solvability of the original non-linear system, thereby exponentially reducing the sample complexity. B.

A Novel Polynomial Reduction Method

Aharonov and Ta-Shma [31] proved that, in general, there exists no efficient method for preparing an arbitrary given quantum state. Ding et al. [29] proposed a reduction method, denoted as Red1, which enables the efficient preparation of the requisite quantum state. To advance this, we propose a novel reduction method, Red2, which guarantees efficient state preparation while concurrently lowering the condition number lower bound. Let X = {x1 , x2 , . . . , xn } be a variable set and F = {f1 , f2 , . . . , fr } ⊆ C[X] be a polynomial system. Solving a Boolean system over the complex field necessitates the field equations HX = {x2i −xi }ni=1 . To mitigate the impact of the reduction on the Macaulay matrix’s spectral norm, we directly fine-tune the Macaulay matrix generated by F ∪ HX . Specifically, we exclusively apply the Red2 to transform F into F ′′ = {f1′′ , f2′′ , . . . , fr′′ } and substitute the r rows generated by f1 , f2 , . . . , fr , leaving the rows generated by HX completely unaltered. Assume F contains at least one polynomial with a nonzero constant term; if all lack constant terms, 0 is trivially a Boolean solution. Let ci denote the constant term of fi , and without loss of generality, assume c1 = ̸ 0. The Red1 method proposed by Ding et al. and our novel Red2 method are detailed as follows: Red1: Let f1′ = − fc11 . For all i ∈ {2, 3, . . . , r}, define ′ fi = fi + ci f1′ . This procedure sets the constant term of f1′ to −1 and eliminates the constant terms in all other polynomials. Red2: Let f1′′ = − fc11 . For all i ∈ {2, 3, . . . , r}, define the following piecewise function to strictly reduce all constant terms to −1: ( if fi has a constant term ci ; − fcii , fi′′ = fi + f1′′ , if fi has no constant term. As is evident from the definitions, these modifications to the r rows of the Macaulay matrix are strictly equivalent to applying a sequence of elementary row operations to both the matrix and its corresponding right-hand side vector. Consequently, the solution space of the Macaulay linear system remains invariant. Harrow et al. [19] did not account for the preparation time of the quantum state |b⟩ when utilizing the HHL algorithm to solve the linear system Ax = b. Chen and Gao [28] proposed a state preparation method applicable to vectors b satisfying specific conditions. Our proposed Red2 ensures that the right-hand side vector of the adjusted Macaulay linear system precisely fulfills these conditions. Appending the equations 0 · x = 1 and 0 · x = 0 to a linear system perfectly preserves the quantum solution state output by the HHL algorithm, which guarantees the validity of Theorem V.2.

7 Theorem V.2. For a linear system Ax = b, if the matrix A ∈ CM ×N and the vector b ∈ {0, 1}M satisfy M = m2v and the component bi = 1 if and only if i = k2v for k = 0, 1, . . . , ρ − 1, then the requisite quantum state for the HHL algorithm can be prepared in O(log2 (M + N )) time. The right-hand side vector bR in the new Macaulay linear system MR mD = bR strictly satisfies the prerequisites of Theorem V.2. Because the system transformations preserve the s-sparsity of the matrix, if the 1-sparse submatrices decomposed from the original matrix exhibit a query complexity of O(γ), the time required for the HHL algorithm to output an ε′ -approximate solution state is strictly bounded by O((log2 (M + N ) + γ)sκb (A)2 /ε′ ). Chen and Gao demonstrated that Macaulay matrices inherently satisfy the condition of γ being sufficiently small, thereby simplifying the ultimate time complexity for solving this system to O((log2 (M + N ))sκ2 /ε′ ), where κ = κb (A).

C.

1.

A Quantum Algorithm for Reduced Macaulay Linear Systems

Algorithmic Framework and Solution Procedure

Based on the theoretical framework established above, we propose an efficient quantum algorithm for finding Boolean solutions of complex polynomial systems via Macaulay matrices (Q-BSCP-M). Given that the uniqueness of the solution is guaranteed when solving the LPSN problem, we omit the generalized version designed to output all solutions. The core of Algorithm 3 utilizes the HHL algorithm to solve the Macaulay linear system MR mD = bR , nδ ∆ where MR ∈ C(r+n)2 ×(2 −1) . In conjunction with the Macaulay matrix modification scheme detailed in Step 15, the vector bR strictly satisfies the conditions in Theorem V.2 corresponding to ρ = r, m = r + n, and v = nδ. Consequently, the requisite quantum state can be prepared in O(log2 (M + N )) time. Chen and Gao demonstrated that the degree-D Macaulay matrix MF ,D generated by F is TF -sparse and inherently admits a 1-sparse decomposition in [28]. When employing Algorithm 3 to find Boolean solutions for F, the initialization phase replaces all variables with degrees greater than 1 with degree-1 variables, yielding the system F1 . Since distinct monomials may map to identical multilinear polynomials, the inequality TF1 ≤ TF holds. Thus, MF1 ,D is at most TF -sparse, and the sparsity of MF2 ,D corresponding to F2 = F1 ∪ HY is bounded by TF + 2n. Applying the Red2 to F1 yields FR , which is subsequently utilized to modify the corresponding r rows in MF2 ,D . The sparsity of the resulting matrix MR is bounded by 2TF + 2n, though we omit the impact of this operation on matrix sparsity in subsequent considerations. The time complexity of Steps 14 and 15 is at most O(r),

establishing the validity of Theorem V.3. Theorem V.3. If VB (F) = ∅, Algorithm 3 outputs ∅; otherwise, it outputs a valid Boolean solution to the system F = 0 with a probability of at least 1 − ε′ . The approximate time complexity of the algorithm is bounded 5 by O(n 2 (n + TF )κ2 log2 ε1′ ), where κ = max κbR (MR ) denotes the maximum condition number of all modified Macaulay matrices MR utilized in Step 16 with respect to the vector bR . In practice, Algorithm 3 serves as a subroutine within Algorithm 4, an efficient quantum algorithm for solving Boolean polynomial systems via Macaulay matrices(QSBP-M). Fig. 1 illustrates the flowchart for solving Boolean systems via Algorithm 4, followed by its properties. Algorithm 4 Q-SBP-M (F , ε′ ) Require: F = {f1 , . . . , fr } ⊂ R2 [X], ε′ ∈ (0, 1). Ensure: a ∈ VF2 (F) ∨ ∅. 1: Y ← X ∪ U(F, 3) 2: F1 ← S(F, 3) ⊆ R2 [Y] b 1 ) ⊆ C[Y] 3: F2 ← C(F 4: a ← Q-BSCP-M(F2 , ε′ ) 5: if a ̸= ∅ then 6: return ProjX a 7: return ∅

Theorem V.4. If VF2 (F) = ∅, Algorithm 4 outputs ∅; otherwise, it outputs a valid solution to the Boolean system F = 0 with a probability of at least 1 − ε′ . The approximate time complexity of the algorithm is bounded 7 7 by O((n 2 + TF2 )κ2 log2 ε1′ ), where κ = max κbR (MR ) denotes the maximum condition number of all Macaulay matrices with respect to specific vectors used while finding Boolean solutions to the system F2 = 0 over the complex field via Algorithm 3. The complexity outlined in Theorem V.4 strictly de′ pends on κ and p 1/ε . By reducing the error rate re′ quirement to ε1 /n and executing multiple iterations, Algorithm 3 exponentially reduces the dependence of the time complexity on 1/ε′ while consistently ensuring a success probability of at least 1 − ε′ .

2.

Bound Analysis of the Condition Number

First, appending p = (2σ − ρ)2v zero rows and zero components to MR ∈ CM ×N and bR respectively yields M1 ∈ C(M +p)×N and b1 ∈ C(M +p)×1 . Subsequently, appending q = 2η − ((r + 2σ − ρ)2v + N ) zero rows and zero components constructs M2 and b2 . The pseudoin
+ + verse M+ = implies M+ M 0 2 2 b2 = MR bR . Given R ∥M2 ∥ = ∥MR ∥ and that the additional non-zero components in b2 compared to bR ensure ∥b2 ∥ ≥ ∥bR ∥, we deduce κb2 (M2 ) ≤ κbR (MR ).

8

Algorithm 3 Q-BSCP-M (F, ε′ ) Require: F = {f1 , . . . , fr } ⊆ C[X], ε′ ∈ (0, 1). Ensure: a ∈ VB (F) ∨ ∅. 1: F1 ← F (mod ⟨x2 − x | x ∈ X⟩), l ← 1, ε′1 ← max{1/2, ε′ } 2: if F1 (1) = 0 then 3: return 1 4: while l ≤ ⌈logε1 ε⌉ do 5: Y ← X, F1 ← FB 6: while F1 ̸= ∅ ∧ F1 (0) ̸= 0 do 7: if F1 ∩ C \ {0} ̸= ∅ then 8: l ← l + 1, break 9: F2 ← F1 ∪ HY , D ← 3#Y, (MF2 ,D , bF2 ,D ) ← ConstructSys(F2 , D) 10:

11: 12:

F

(MR , bR ) ←−R− ReConstructSys(F2 , D), |c mD ⟩ ← HHL(MR , bR , Quk Measure |e⟩ ←−−−−− |c mD ⟩, mD̄,k = i=1 xni ← Identify(|e⟩) xni ← 1 (∀i ∈ {1, . . . , uk }), F1 ← F1 x =1 \ {0}, Y ← Y \ {xni | i = 1, . . . , uk } FR ← Red2(F1 ),

13: for i = 1 to n do 14: if xi ∈ Y then 15: ai ← 0 16: else 17: ai ← 1 18: return a = (a1 , a2 , . . . , an ) 19: return ∅

p ε′1 /n)

ni

To satisfy the HHL algorithm’s requirement for a selfadjoint transformation, the system solved  in practice  is 0 M2 formulated as M3 y = b3 , where M3 = and MH 2 0    0 b2 + b3 = . This formulation yields M3 b3 = 0 M+ 2 b2 + + and ∥M3 b3 ∥ = ∥M2 b2 ∥. Combined with ∥M3 ∥ = ∥M2 ∥ and ∥b3 ∥ = ∥b2 ∥, it follows that κb3 (M3 ) ≤ κbR (MR ). This demonstrates that preprocessing does not degrade the linear system but rather enhances its stability. Therefore, directly evaluating the condition number upper bound of the original reduced system κbR (MR ) is both reasonable and sufficiently rigorous. In Fig. 1, let MmD = b denote the Macaulay linear system corresponding to F4 . The reduction driven by F3′′ is equivalent to elementary row operations; thus, the reduced system MR mD = bR shares the identical solu+ tion space and minimal norm solution M+ R bR = M b with the original system. As detailed in Section V B, bR contains exactly TF − 2r non-zero components equal 1 to 1, yielding ∥bR ∥ = (TF − 2r) 2 . Adopting the assumptions ∥MR ∥ = ∥M∥ and ∥M∥ ≥ 1, we obtain 1 κbR (MR ) ≥ (TF − 2r)− 2 ∥M+ b∥. If the Boolean system possesses a unique solution a with Hamming weight h, the minimal norm solution output by the HHL al
gorithm contains D+h − 1 non-zero components. By h selecting the full solving degree D = 3n, the lower bound of the condition number is strictly determined   12
−1 as κbR (MR ) ≥ (TF − 2r) 2 3n+h . − 1 h Consider a 3-sparse Boolean polynomial system comprising 5 variables and 27 polynomials. Assume the sys-

tem has undergone a multilinear transformation, and the corresponding Macaulay linear system is fully solvable when D = 2, at which point d¯ = 1 and D̄ = 3. After appending the field polynomials, each polynomial generates 32 rows, constructing a Macaulay matrix with exact dimensions of 1024×1023, where the first 864 rows originate from the complex field polynomials and the subsequent 160 rows from the field polynomials. Based on the constant term distribution and equivalent transformation rules, we designed a greedy search algorithm driven by iterative optimization and structural constraints. Through 106 iterations, we successfully constructed a Macaulay matrix instance featuring a specific block-sparsity pattern and a minimized spectral norm bounded by ∥M∥ ≈ 4.71, visually represented in Fig. 2. The non-linear Boolean system F corresponding to this matrix M comprises 23 polynomials with constant terms and 4 without, yielding 81 terms. In this case, √ the reduced right-hand side vector satisfies ∥bR ∥ = 27. Adopting Ding et al.’s assumption that ∥MR ∥ = ∥M∥,   12
−1 we have (TF − 2r) 2 3n+h −1 < κbR (MR ) < h   12
3n+h − 1 . This confirms that under our reduction, h the condition number of the Macaulay linear system with respect to the right-hand side vector can strictly surpass the theoretical lower bound established by Ding et al. Obtaining MR intrinsically equates to applying elementary row operations to the original matrix M. Swapping two rows and dividing by the constant 1 perfectly preserve the spectral norm. In the worst-case scenario, adding a row containing a constant term to the remaining TF − 2r − 1 rows devoid of constant terms strictly restricts the scaling of the spectral norm within the in-

9

Input: Boolean system F = {f1 , . . . , fr }

Convert to 3-sparse Boolean system F1 Preprocessing Phase

Transform to polynomial system F2 ⊆ C[X]

→ xi ) Multilinearization (xm i Generate system F3 = {f1′ , . . . , fr′ }

Define extended system F4 = F3 ∪ HX Algorithm 4

Polynomial Reduction Apply Red2 on F3 to obtain F3′′ = {f1′′ , . . . , fr′′ }

Matrix Construction Construct degree-D Macaulay linear system MF4 ,D mD = bF4 ,D

Algorithm 3

Row Modification Replace rows generated by {fi′ } in the system with rows from {fi′′ } Result: MR mD = bR

Solve using HHL algorithm

Output: Solution for X

FIG. 1. Macaulay-based quantum algorithm for Boolean systems. 1

1

terval [O((TF − 2r)− 2 ), O((TF − 2r) 2 )]. Combined with the fact that this reduction amplifies ∥b∥ by a factor of 1 O((TF − 2r) 2 ), it fundamentally avoids escalating the condition number and theoretically holds the potential to decrease it. The Red1 employed by Ding et al. neglected the impact of row operations on the matrix norm. Incorporating this factor, the condition number interval under the Red1 is approximately    12
−1 (TF − 2r) 2 3n+h − 1 ∥M∥, h    12
1 3n+h 2 (TF − 2r) − 1 ∥M∥ . h

Conversely, our Red2 strictly compresses this interval to    12
−1 3n+h (TF − 2r) − 1 ∥M∥, h    12
3n+h − 1 ∥M∥ . h The significant reduction across both the upper and lower bounds conclusively demonstrates the superiority of our reduction method.

3.

Quantum Time Complexity Bounds for

10

(a)

(b)

FIG. 2. Visualization of the Macaulay matrix with dimensions 1024 × 1023. (a) The distribution of element values. (b) The sparsity pattern representing non-zero entries.

D.

Solving the LPSN Problem

1.

According to Theorem V.4, the time complexity of employing Algorithm 4 to solve the system F is bounded 7 7 by O((n 2 + TF2 )κ2 log2 ε1′ ). A single sample under a degree-d structured noise polynomial yields a Boolean
Pd equation with at most i=0 ni terms. Deduced from Section V A, acquiring ⌈2m ln 1ε ⌉ samples guarantees the unique solvability of the Boolean system with a probability of
at least 1 − ε. At this point, we have TF ≤ Pd n 1 m i=0 i ⌈2 ln ε ⌉. To achieve a success probability of ′ at least (1 − ε)(1  − ε ), the runtime of  Algorithm 4 is 7

7

7

bounded by O 2 2 m n 2 d κ2 ln 2 1ε log2 ε1′ .

Before any variable assignments, initially solving the Macaulay linear system  M
R mD = bR dictates −1 3n+h 2 κbR (MR ) ≥ (TF − 2r) − 1 . Since TF −2r = h
h O(2m nd ln 1ε ), and for all h ≥ 1, the inequality 3n+h ≤ h   h
e(3n+h) 3n+h 2 ≤ holds, we deduce κbR (MR ) ≥ h h
h 2−m h3 nh−d ln−1 1ε . Therefore, utilizing Algorithm 4 recovers the secret vector in the LPSN problem with a ′ probability of at  least  (1 − ε)(1 − ε ) in a time complexity  5

5

5

bounded by O Ω 2 2 m h−h n 2 d+h ln 2 1ε log2 ε1′

.

A Quantum Algorithm for Reduced Boolean Macaulay Linear Systems Algorithmic Framework and Solution Procedure

By replacing the Macaulay matrix utilized in Algorithm 3 with the Boolean Macaulay matrix, we obtain an efficient quantum algorithm for finding Boolean solutions of complex polynomial systems via Boolean Macaulay matrices (Q-BSCP-BM), and prove its properties. Analogous to the reduction process for standard Macaulay matrices detailed previously, we directly generate the Boolean Macaulay matrix from F1 and apply the Red2 to obtain the new system FR . We subsequently utilize FR to substitute the corresponding r rows in the original matrix, yielding a new Boolean Macaulay matrix BR . Because this procedure strictly equates to applying identical elementary row operations to both the matrix and the right-hand side vector, the solution space of the Boolean Macaulay linear system remains completely invariant. Combining the results of Ding et al. [29] with the reduction process, the sparsity of the reduced matrix BR remains bounded by O(r · TF ). Theorem V.5. When the equation system F = 0 admits a Boolean solution, Algorithm 5 outputs a Boolean solution with a probability of at least 1 − ε′ . Its run5 time complexity is bounded by O(n 2 rTF κ2 log2 ε1′ ), where κ = max κbR (BR ) denotes the maximum condition number of all Boolean Macaulay matrices BR utilized in Step

11

Algorithm 5 Q-BSCP-BM (F , ε′ ) Require: F = {f1 , . . . , fr } ⊆ C[X]; ε′ ∈ (0, 1). Ensure: a ∈ VB (F) ∨ ∅. 1: F1 ← F (mod ⟨x2 − x | x ∈ X⟩), l ← 1, ε′1 ← max{1/2, ε′ } 2: if F1 (1) = 0 then 3: return 1 4: while l ≤ ⌈logε′ ε′ ⌉ do 1 5: Y ← X, F1 ← FB 6: while F1 ̸= ∅ ∧ F1 (0) ̸= 0 do 7: if F1 ∩ C \ {0} ̸= ∅ then 8: l ← l + 1, break 9: d ← #Y, (BF1 ,d , bF1 ,d ) ← ConstructSys(F1 , d) 10:

11: 12:

p F (BR , bR ) ←−R− ReConstructSys(F1 , d), |c md ⟩ ← HHL(BR , bR , ε′1 /n) Q Measure uk |e⟩ ←−−−−− |c md ⟩, md,k ¯ = i=1 xni ← Identify(|e⟩) xni ← 1 (∀i ∈ {1, . . . , uk }), F1 ← F1 x =1 \ {0}, Y ← Y \ {xni | i = 1, . . . , uk }

FR ← Red2(F1 ),

13: for i = 1 to n do 14: if xi ∈ Y then 15: ai ← 0 16: else 17: ai ← 1 18: return a = (a1 , a2 , . . . , an ) 19: return ∅

ni

15 with respect to the vector bR . Proof. Algorithm 5 perfectly mirrors the structure of Algorithm 3, exclusively substituting the Boolean Macaulay matrix and omitting field polynomials. Step 15 dominates the overall time complexity. It utilizes the HHL algorithm to solve the Boolean Macaulay linear system BR mD = bR , where the matrix dimensions reach at most r2n × (2n − 1). The vector bR strictly satisfies the conditions in Theorem V.2 corresponding to ρ = r, m = r, and v = n, bounding the state preparation time by O(log2 ((r + 1)2n − 1)). According to Chen and Gao [28], a single execution p of this step requires at most c log2 ((r + 1)2n − 1)rTF κ2 n/ε′1 time. In the worst-case scenario where variable assignments fail to reduce matrix sparsity, the inner loop executes at most n − 1 times, while the outer loop executes at most ⌈logε′1 ε′ ⌉ times. Setting ε′1 = 1/2 and applying logarithmic scaling bounds the total time complexity strictly 5 by O(n 2 rTF κ2 log2 ε1′ ). By substituting Algorithm 5 for Algorithm 3 within Algorithm 4, we obtain Algorithm 6, an efficient quantum algorithm for solving Boolean polynomial systems via Boolean Macaulay matrices (Q-SBP-BM), and prove its properties. Fig. 3 delineates the complete flowchart of this algorithm. Theorem V.6. When the Boolean system F = 0 admits a solution, Algorithm 6 outputs a solution with a probability of at least 1 − ε′ . Its runtime complexity is bounded 5 5 ′ by O((n 2 + TF2 )rTF κ2 log2 ε1′ ), where κ = max κb′R (BR ) denotes the maximum condition number of all Boolean ′ Macaulay matrices BR utilized with respect to specific ′ vectors bR during the process of finding Boolean solutions

to the system F2 = 0 over the complex field via Algorithm 5. Proof. Transforming the Boolean polynomials into a 3sparse partition set in Step 2 and converting them into complex-field polynomials in Step 3 both require b 1 )), the O(TF ) time. Since VF2 (F) = ProjX VB (C(F problem reduces exclusively to finding the Boolean solutions of F2 . Employing an s-sparse partition bounds the variable count by n + TF /s and the term count s by TF s 2 . Following Theorem V.5, Step 4 requires s 5 O((n + TsF ) 2 rTF s 2 κ2 log2 ε1′ ) time. In practice, setting s = 3 strictly bounds the overall time complexity of Algo5 5 rithm 6 by O((n 2 + TF2 )rTF κ2 log2 ε1′ ). Algorithm 6 Q-SBP-BM (F , ε′ ) Require: F = {f1 , . . . , fr } ⊂ R2 [X], ε′ ∈ (0, 1). Ensure: a ∈ VF2 (F) ∨ ∅. 1: Y ← X ∪ U(F, 3) 2: F1 ← S(F, 3) ⊆ R2 [Y] b 1 ) ⊆ C[Y] 3: F2 ← C(F 4: a ← Q-BSCP-BM(F2 , ε′ ) 5: if a ̸= ∅ then 6: return ProjX a 7: return ∅

2.

Bound Analysis of the Condition Number

Assuming variable assignments remain unknown, applying the Red2 transforms the system into BR md = bR . Following the analogous analysis in Sections II C 1 and

12

Input: Boolean system F = {f1 , . . . , fr }

Convert to 3-sparse Boolean system F1 Preprocessing Phase

Transform to polynomial system F2 ⊆ C[X]

Multilinearization (xm → xi ) i Generate system F3 = {f1′ , . . . , fr′ }

Matrix Construction Construct degree-d Boolean Macaulay linear system BF3 ,d md = bF3 ,d

Polynomial Reduction Apply Red2 on F3 to obtain F3′′ = {f1′′ , . . . , fr′′ }

Algorithm 6

Algorithm 5

Row Modification Replace rows generated by {fi′ } in the system with rows from {fi′′ } Result: BR md = bR

Solve using HHL algorithm

Output: Solution for X

FIG. 3. Boolean Macaulay-based quantum algorithm for Boolean systems. 1

+ V C 2, we have BR bR = B + b and ∥bR ∥ = (TF − 2r) 2 . Retaining the assumptions that ∥BR ∥ = ∥B∥ and ∥B∥ ≥ 1, 1 we deduce κbR (BR ) ≥ (TF − 2r)− 2 ∥B + b∥. When the Boolean system admits a unique solution a with Hamming weight h, the condition number lower bound is 1 1 κbR (BR ) ≥ (TF − 2r)− 2 (2h − 1) 2 . Consider a 3-sparse Boolean polynomial system comprising 4 variables and 512 polynomials. Assume all polynomials contain constant terms. Each polynomial generates 16 rows, forming an 8192×15 Boolean Macaulay matrix. By modifying the search algorithm based on structural constraints, 106 iterations yielded a matrix instance with a minimized spectral norm bounded by ∥B∥ ≈ 21.03, structurally depicted in Fig. 4. The system corresponding to the √ aforementioned matrix B satisfies TF = 1536 and ∥bR ∥ = 512. Similarly, it can −1

1

1

be proven that TF 2 (2h − 1) 2 < κbR (BR ) < (2h − 1) 2 ,

conclusively demonstrating that our reduction can strictly surpass the theoretical condition number lower bound established by Ding et al. Incorporating the impact of row operations on the matrix norm, the condition number interval under the 1 1 Red1 is approximately [(TF − 2r)− 2 (2h − 1) 2 ∥M∥, (TF − 1 1 2r) 2 (2h −1) 2 ∥M∥]; whereas the Red2 strictly compresses 1 1 this interval to [(TF −2r)−1 (2h −1) 2 ∥M∥, (2h −1) 2 ∥M∥]. The significant optimization of both the upper and lower bounds further validates the superiority of our reduction method.

3.

Quantum Time Complexity Bounds for

13

(a)

(b)

FIG. 4. Visualization of the Boolean Macaulay matrix with dimensions 8192 × 15. (a) The distribution of element values. (b) The sparsity pattern representing non-zero entries.

Solving the LPSN Problem

According to Theorem V.6, the time complexity of employing Algorithm 6 to solve the system F is bounded by 5 5 O((n 2 + TF2 )rTF κ2 log2 ε1′ ). When possessing ⌈2m ln 1ε ⌉ samples, to achieve a success probability of at least ′ (1 −  ε)(1 − ε ), the runtimeof Algorithm 6 is bounded by 9

7

7

O 2 2 m n 2 d κ2 ln 2 1ε log2 ε1′ .

Before any variable assignments, initially solving the Boolean Macaulay linear system BR md = bR dictates κbR (BR )2 ≥ TF−1 (2h − 1). Since TF − 2r = O(2m nd ln 1ε ), we deduce κbR (BR )2 ≥ 2h−m n−d ln−1 1ε . Therefore, utilizing Algorithm 6 recovers the secret vector in the LPSN problem with a probability of at ′ least  (1  − ε)(1 − ε ) in a time complexity bounded by 7

5

5

O Ω 2 2 m+h n 2 d ln 2 1ε log2 ε1′

VI.

.

QUANTUM RESOURCE EVALUATION A.

Quantum Resource Estimate

Scherer et al. [27] provided the first concrete logical resource estimate for the HHL algorithm under the standard quantum-circuit model. Their conclusion can be summarized as follows: even in the idealized case that counts only the logical level, the HHL algorithm requires several hundred logical qubits and a gate count and circuit depth

exceeding the order of 1025 ; these resources are dominated by the Suzuki–Trotter time-splitting of Hamiltonian simulation, depend critically on the condition number κ and the precision ε, and depend only logarithmically on the matrix size N . In other words, what sets the order of magnitude of the HHL algorithm’s resources is not the problem size itself but κ and ε. The core step of our Algorithm 3 and Algorithm 5 invokes the HHL algorithm to solve a Macaulay and a Boolean-Macaulay linear system, and their dominant resources are inherited entirely from this primitive, on which basis we evaluate the required qubit count and circuit size in a fine-grained manner. To make this evaluation concrete, Fig. 5 depicts the registerlevel circuit of one HHL-core invocation inside Algorithm 3 (A = MR ) or Algorithm 5 (A = BR ): the number of horizontal wires directly exhibits the circuit width, while the macro box eiAt encapsulates the two nested multipliers that dominate the circuit depth, which are expanded in Figs. 6 and 7 below. The qubit count, namely the circuit width, is obtained by summing the sizes of the registers used by the HHL algorithm, i.e., the wires of Fig. 5. To solve a linear system, the HHL algorithm requires an index register encoding the solution vector, whose size equals the binary logarithm of the number of matrix columns; a phase register storing the eigenvalues, whose size is jointly determined by precision and condition number and is taken as nev = ⌈log2 (κ/ε′ )⌉+ O(1); an ancilla register of the same size storing the reciprocals of the eigenvalues; a single-qubit ancilla for the controlled rotation; and several fixed-point arithmetic

14 index reg. |0⟩⊗nidx phase reg. |0⟩⊗nev

Prep |bR ⟩

e−iAt

eiAt

H ⊗nev

QFT†

eigen-inverse reg. |0⟩⊗nev

H ⊗nev

QFT

(1/λ)†

1/λ

rotation anc. |0⟩

Ry 2 arcsin C λ

FIG. 5. Register-level quantum circuit of one HHL-core invocation inside Algorithm 3 (A = MR ) or Algorithm 5 (A = BR ). The Red2 reduction and the construction of the reduced matrix A ∈ {MR , BR } and right-hand side bR are performed classically and are not depicted. Between successive invocations a monomial is identified, variables are assigned classically, and a smaller system is reconstructed and re-solved. The two measurements (index register and rotation ancilla) occur at the same final time step, after the eigenvalue computation has been fully uncomputed. The total number of wires realizes the circuit width W = nidx + 2 nev + O(bfix ) + O(1) analyzed in the text, with nidx = n⌈log2 (3n + 1)⌉ for Algorithm 3 and nidx = n for Algorithm 5.

ancilla registers of bit width bfix . The circuit width can thus be written as W = nidx + 2⌈log2 (κ/ε′ )⌉ + O(bfix ) + O(1), where nidx is the index-register size and constitutes the only essential difference between the two matrix types, as annotated in the caption of Fig. 5. For the Macaulay linear system solved by Algorithm 4, the qubit count is governed mainly by the number of columns of the Macaulay matrix. This matrix MR ∈ nδ n∆ C(r+n)2 ×(2 −1) has 2n∆ − 1 columns, so the index register requires nidx = n∆ qubits, where ∆ = ⌈log2 (3n + 1)⌉ corresponds to the full solving degree D = 3n. Substituting into the expression above yields the circuit width WMac ≈ n ⌈log2 (3n + 1)⌉ + 2⌈log2 (κ/ε′ )⌉ + O(bfix ), which grows quasi-linearly in the number of unknowns n. For the Boolean-Macaulay linear system solved by Algorithm 6, the qubit count is reduced further. This matrix BR has dimensions at most r2n × (2n − 1) with 2n − 1 columns, so the index register requires only nidx = n qubits. Substituting into the expression above yields the circuit width WBMac ≈ n + 2⌈log2 (κ/ε′ )⌉ + O(bfix ), which grows only linearly in the number of unknowns n, saving a factor of about ⌈log2 (3n + 1)⌉ in index overhead compared with the Macaulay case. When κ and ε′ take common magnitudes, this width is on the order of a few hundred, consistent with the baseline of [27]. The circuit depth and total gate count are determined by the nested loops within the HHL algorithm, whose dominant term is the Trotter time-splitting of Hamiltonian simulation. Specifically, the total gate count and depth are obtained by multiplying the layers in turn: D ∼ NHHL × NQPE × r ms × gslice , where NHHL is the number of HHL-algorithm calls, NQPE the number of phase-estimation iterations, ms the number

q0

H

q1

H

q2

H

QFT†

.. . qnev −1 index |ψ⟩

.. . H

0

ei2 At

1

ei2 At

2

ei2 At

···

ei2

nev −1

At

FIG. 6. Inside the box eiAt of Fig. 5: the complete QPE controlled-power cascade, constituting depth source (I). The geometrically increasing controlled powers contribute the multiplicative factor NQPE ∼ 2nev ∼ O(κ/ε′ ) to the circuit depth.

of 1-sparse submatrices, and gslice the gate count per Trotter slice, which includes the gates needed to compute the matrix entries. The first nested multiplier, NQPE , is visualized in Fig. 6, which expands the macro box eiAt of Fig. 5 into the complete QPE controlled-power j cascade: the nev controlled powers ei2 At accumulate a total evolution of NQPE ∼ 2nev ∼ O(κ/ε′ ) elementary time steps, in exact agreement with the κ-dependence entering through the Hamiltonian-simulation time below. The second nested multiplier originates from the Suzuki– Trotter decomposition of each controlled power, shown in Fig. 7: every evolution eiAτ is realized by ms one-sparse (Aj ) walk steps Uwalk , each sandwiched between an oracle call OA and its inverse, and r consecutive such slices reproduce eiAτ to precision ε′ , giving exactly the factor r ms in the depth product above. The time-splitting factor is
1+1/2k  ′ 1/2k r = 5 k−1/2 2ms ∥A∥t ε ,

t ∼ O(κ/ε′ ).

Taking the Suzuki order k = 2 and the sparse decomposition s = 3, and noting the lack of parallelism in the HHL algorithm [27], the circuit depth and total gate count are of the same order; multiplying the layers of Figs. 5–7 in

15 phase ctrl t[j] (A )

working reg. OA

(A

···

1 Uwalk

† OA

ms Uwalk

OA

) † OA

oracle anc. |0⟩⊗bfix

FIG. 7. Inside one eiAτ : the Suzuki–Trotter expansion, constituting depth source (II). Two 1-sparse steps (bands A1 , . . . , Ams ) are shown explicitly; ms such steps form one Trotter slice, and r consecutive slices realize eiAτ , giving the factor r ms in the depth estimate.

turn, their magnitude coincides exactly with the time complexities given by Theorems V.4 and V.6, which validates our theoretical analysis at the circuit level. For the Macaulay linear system, the circuit depth and gate count are of the same order as in Theorem V.4. Here the matrix sparsity is at most 2TF + 2n, and by [28] it admits an efficient 1-sparse decomposition, so that   7/2 DMac ∼ O (n7/2 + TF ) κ2 log2 ε1′ , where the condition number satisfies κ ≥ (TF −

1/2 2r)−1/2 3n+h −1 . h For the Boolean-Macaulay linear system, the circuit depth and gate count are of the same order as in Theorem V.6. Here the matrix sparsity is O(rTF ), so that   5/2 DBMac ∼ O (n5/2 + TF ) rTF κ2 log2 ε1′ , where the condition number satisfies κ ≥ (TF − 2r)−1/2 (2h − 1)1/2 . The above results show that both the circuit depth and the gate count grow as the square of the condition number, so the optimization of the condition number by Red2 translates directly into a resource saving. On the one hand, as is evident from Figs. 6 and 7, the condition number enters the circuit depth through the Hamiltoniansimulation time t ∼ κ/ε′ and the time-splitting factor r ∼ κ1+1/2k ; on the other hand, it appears as κ2 in the total complexity. Relative to the Red1 employed by Ding et al. [29], our Red2 tightens the upper and lower bounds of the condition number with respect to the right-handside vector without altering the solution space of the linear system, thereby lowering the circuit depth and gate count by a corresponding amount. This is precisely the resource-level manifestation of our condition-number optimization. Combining the two aspects of qubits and circuit size, we can compare the resources of the two quantum algorithms. In terms of qubits, the index register of the BooleanMacaulay system is only n, markedly smaller than the n⌈log2 (3n + 1)⌉ of the Macaulay system; in terms of the condition number, the former depends on 2h and the
3n+h latter on , so when the Hamming weight h of the h solution is small, the Boolean-Macaulay system has a

lower condition-number bound and a smaller circuit size. Thus, with respect to resource consumption, the BooleanMacaulay system is generally preferable, whereas in the specific parameter regimes identified in Section VII the Macaulay system may still prevail; the two can be selected according to the algorithm-selection strategy.

B.

Feasibility and Quantum Advantage

The above resource estimate shows that our quantum algorithm is implementable at the logical level. The circuit width grows linearly or quasi-linearly in the number of unknowns n, and only logarithmically in the condition number and precision; the circuit depth and gate count are of the same order as the time complexities given by Theorems V.4 and V.6, constituting finite and explicitly quantifiable closed-form expressions whose magnitude is governed chiefly by the condition number κ. The circuit framework of Figs. 5–7 makes this claim fully constructive: every layer of the depth product corresponds to an explicitly drawn sub-circuit. Hence the resource requirements of our quantum algorithm are definite and computable, not merely asymptotically meaningful. The above estimate is conservative and admits further room for compression. The Hamiltonian-simulation calibration adopted here follows the early technique used in [27]; employing the advanced Hamiltonian-simulation methods we already cite, namely those of Berry et al. [21] and Childs et al. [22], which improve the precision dependence to O(log(1/ε)) and reduce the sparsity dependence to near-linear, would substantially further lower the circuit depth and gate count. Moreover, by lowering the p error requirement to ε′1 /n and iterating, our strategy compresses the 1/ε′ dependence to logarithmic, superior to the 1/ε′ of the naive HHL algorithm, rendering the precision-direction cost more controllable. Taken together, our resource evaluation supports the potential of the quantum algorithm to outperform classical algorithms. Since the circuit size grows as the square of the condition number, and our Red2 tightens the condition-number interval relative to Ding et al. [29], a corresponding reduction in resources follows; combined with the √ complexity comparison in Section VII, even at h = Θ( n) our quantum algorithm retains the potential to outperform classical algorithms in specific parameter regimes. It follows that, with sparsity s = 3 and a fixed number of unknowns n, the required qubit count is linear or quasi-linear in n and the circuit size is controllable, so that a controllable implementation cost and a potential speedup hold simultaneously.

VII.

COMPARATIVE ANALYSIS OF CLASSICAL AND QUANTUM ALGORITHMS

Table I summarizes the requirements regarding the correlation polynomial, sample complexity, and time com-

16 plexity of the four algorithms for solving the LPSN problem under both random and adversarial structured noise patterns. The success probabilities of the classical and quantum algorithms are at least 1 − ε and (1 − ε)(1 − ε′ ), respectively. To facilitate the comparison of time complexities, we extract their dominant exponential growth terms. Let n denote the secret vector dimension, h its Hamming weight, m the number of correlated noise variables, and d the correlation polynomial degree. We define Tc1 = 2d n3d+1 and Tc2 = 2m+d n3d as the dominant time complexity terms for 5 5 Classical Algorithms 1 and 2, and Tq1 = 2 2 m h−h n 2 d+h 7 5 and Tq2 = 2 2 m+h n 2 d for Quantum Algorithms 4 and 6, respectively. Due to space constraints, this paper exclusively presents the experimental results comparing the time complexities of Classical Algorithm 2 and the quantum algorithms.

A.

Selection Strategies for Classical Algorithms

Concerning applicable noise patterns, Classical Algorithm 2 exhibits broader applicability, functioning under both random and adversarial structured noise patterns, whereas Classical Algorithm 1 is exclusively viable for the random structured noise pattern. With respect to sample complexity, under the random structured noise pattern, the sample size required by Classical Algorithm 1 is merely a 2−m fraction of that required by Classical Algorithm 2, demonstrating a substantial advantage. In terms of runtime, omitting logarithmic factors, conT sider that the condition Tcc1 ≥ 1 is equivalent to n ≥ 2m . 2 When parameters satisfy the following conditions, we can determine the performance superiority: (1) n < 2m , Classical Algorithm 1 outperforms Classical Algorithm 2; (2) n = 2m , the upper bounds of their time complexities are identical; (3) n > 2m , Classical Algorithm 2 outperforms Classical Algorithm 1. Consequently, we provide the following selection strategies. Under the random structured noise pattern, Classical Algorithm 1 is advantageous when the available sample
Pd size is relatively small (e.g., S = Θ(( i=1 ni +log2 1ε )2d )) or parameters satisfy n < 2m . Conversely, when an ample sample size is accessible (e.g., S = Ω((nd + log2 1ε )2m+d )) and n > 2m , Classical Algorithm 2 is preferable. Under the adversarial structured noise pattern, Classical Algorithm 2 remains the uniquely applicable classical approach, guaranteeing recovery given sufficient samples.

a concise comparison, we exclusively consider the adversarial structured noise pattern here, as the required complexities remain strictly identical across both patterns. With respect to sample complexity, both algorithms merely require guaranteeing the uniqueness of the solution to the system of non-linear Boolean equations. Consequently, their sample requirements are strictly identical, both necessitating exactly ⌈2m ln 1ε ⌉ queries to the oracle Q2 (n, m, P, µ, s) to achieve a success probability of at least (1 − ε)(1 − ε′ ). In terms of runtime, omitting logarithmic factors, T consider that the condition Tqq1 ≥ 1 is equivalent to

C.

1.

Selection Strategies for Quantum Algorithms

Comparative Analysis and Advantage Assessment of Classical versus Quantum Algorithms

Classical Algorithms versus the Quantum Algorithm for Macaulay Linear Systems

Regarding sample complexity, the sample size required by Quantum Algorithm 4 is merely a 2m−d n−d fraction of that required by Classical Algorithm 1, demonstrating a substantial advantage. In terms of runtime, omitting logarithmic factors, T consider that the condition Tqc1 ≥ 1 is equivalent to 5

B.

2

h log2 h+m+h

h n≥2 , which can also be elegantly expressed as m ≤ h(log2 n − log2 h − 1). When parameters satisfy the following conditions, we can determine the performance superiority: (1) m > h(log2 n − log2 h − 1) (or h log2 h+m+h h n < 2 ), Quantum Algorithm 4 outperforms Quantum Algorithm 6; (2) m = h(log2 n − log2 h − 1), the upper bounds of their time complexities are comparah log2 h+m+h h ble; (3) m < h(log2 n − log2 h − 1) (or n > 2 ), Quantum Algorithm 6 outperforms Quantum Algorithm 4. Consequently, we provide the following selection strategies. Because the sample complexities are identical, the selection hinges entirely on the parameter regimes governing execution speed. Quantum Algorithm 4 is preferable when the sample noises are tightly correlated and the number of correlated noise variables is relatively large (e.g., m = Ω(log2 n) or bounded by m > 2e nln 2 ). Conversely, when the relationship between sample noises is loose and the number of correlated noise variables is relatively small (e.g., m = O(log2 n)), Quantum Algorithm 6 is the superior choice.

1

d

2d− 2 m hh ≥ nh− 2 −1 . When parameters satisfy the following conditions, Quantum Algorithm 4 holds the potential to outperform Classical Algorithm 1: (1) h < 2d−5m+2h log

Concerning applicable noise patterns, both Quantum Algorithm 4 and Quantum Algorithm 6 exhibit identical capabilities, functioning seamlessly under both random and adversarial structured noise patterns. To facilitate

h

2 d 2h−d−2 , 2 + 1 and n ≥ 2 ( d2 + 1) log2 ( d2 + 1) + d ≥ 52 m, 2d−5m+2h log2 h

(2) h = (3) h >

d 2 + 1 d 2 + 1

and and

2h−d−2 1≤n≤2 . Considering that practically constructed Boolean equa-

17 TABLE I. Comparison of algorithms under random and adversarial structured noise patterns. Algorithm

Noise pattern Algebraic constraints

Random Adversarial Random Classical algorithm 2 [6] Adversarial Random Quantum algorithm 4 Adversarial Random Quantum algorithm 6 Adversarial Classical algorithm 1 [6]

— — — ✓

Sample complexity
P Ω(( di=1 ni + log2 1ε )2d ) —
P Ω(( di=1 ni + log2 1ε )2m+d )
P ′ ′ Ω(( di=1 ni + log2 1ε )2d )

✓

Ω(2m ln 1ε )

O(Ω(2 2 m h−h n 2 d+h ln 2 1ε log2 ε1′ ))

✓

Ω(2m ln 1ε )

O(Ω(2 2 m+h n 2 d ln 2 1ε log2 ε1′ ))

tions containing at most O(nt ) terms and satisfying 1 ≤ t ≤ d, the dominant term of Quantum Algorithm 4 5 5 reduces to Tq′1 = 2 2 m h−h n 2 t+h , whereas Classical AlgoT

rithm 1 remains unaffected. Considering Tc′1 ≥ 1, when q1 parameters satisfy the following conditions, Quantum Algorithm 4 holds a potential advantage: (1) 52 t + h < 3d + 1 2d−5m+2h log2 h

and n ≥ 2 5t+2h−6d−2 , (2) 52 t + h = 3d + 1 and (3d+1− 52 t) log2 (3d+1− 25 t)+d ≥ 52 m, (3) 52 t+h > 3d+1 2d−5m+2h log2 h

and 1 ≤ n ≤ 2 5t+2h−6d−2 . Comparing Classical Algorithm 2 with Quantum Algorithm 4, the sample sizes required by Quantum Algorithm 4 under random and adversarial structured noise patterns are merely (2n)−d and 2m−d n−d fractions of those for Classical Algorithm 2, respectively. Regarding T runtime, consider that the condition Tqc2 ≥ 1 is equivalent 3

2d−3m+2h log2 h 2h−d

, (2) h = d2 and d log2 ( d2 ) + 2d ≥ 3m, 2d−3m+2h log2 h

2h−d (3) h > d2 and 1 ≤ n ≤ 2 . Fig. 8 validates this conclusion. Under the constraint of the actual term T parameter t, considering Tc′2 ≥ 1, when parameters satisfy q1 the following conditions, Quantum Algorithm 4 holds a po2d−3m+2h log2 h tential advantage: (1) 52 t+h < 3d and n ≥ 2 5t+2h−6d , (2) 52 t + h = 3d and (3d − 25 t) log2 (3d − 52 t) + d ≥ 23 m, (3)

5 2 t + h > 3d and 1 ≤ n ≤ 2

2.

2d−3m+2h log2 h 5t+2h−6d

.

Classical Algorithms versus the Quantum Algorithm for Boolean Macaulay Linear Systems

Because the sample requirements for Quantum Algorithm 6 and Quantum Algorithm 4 are strictly identical, Quantum Algorithm 6 maintains a substantial sample complexity advantage over the classical algorithms. Comparing Classical Algorithm 1 with Quantum AlT gorithm 6, consider that the condition Tqc1 ≥ 1 is equiv2

d

7

O((nd + log2 1ε )2d n2d+1 ) — O((nd + log2 1ε )2m+d n2d ) ′ ′ ′ O((nd + log2 1ε )2m+d n2d ) 5

5

7

5

5

5

the dominant term of Quantum Algorithm 6 reduces 7 5 T to Tq′2 = 2 2 m+h n 2 t . Considering Tc′1 ≥ 1, when parame7m+2h−2d 6d−5t+2

q2

ters satisfy n ≥ 2 , Quantum Algorithm 6 holds a potential advantage. Comparing Classical Algorithm 2 with Quantum AlgoT rithm 6, consider that the condition Tqc2 ≥ 1 is equivalent 2

5

d

5m+2h−2d

d to n 2 ≥ 2 2 m+h−d , which implies n ≥ 2 . When parameters satisfy this bound, Quantum Algorithm 6 holds the potential to outperform Classical Algorithm 2. Fig. 9 validates this theoretical result. Restricted by the T parameter t, considering Tc′2 ≥ 1, when parameters satisfy 5m+2h−2d

q2

n ≥ 2 6d−5t , Quantum Algorithm 6 holds a potential advantage.

1

d

to 2d− 2 m hh ≥ nh− 2 . When parameters satisfy the following conditions, Quantum Algorithm 4 holds the potential to outperform Classical Algorithm 2: (1) h < d2 and n≥2

Time complexity

7m+2h−2d

alent to n 2 +1 ≥ 2 2 m+h−d , which implies n ≥ 2 d+2 . When parameters satisfy this bound, Quantum Algorithm 6 holds the potential to outperform Classical Algorithm 1. Subject to the actual term parameter t,

VIII.

CONCLUSION AND FUTURE WORK

In this paper, we conduct a systematic study of classical and quantum approaches to the LPSN problem in the sample-restricted regime. On the classical side, by combining the binary Schwartz–Zippel lemma with inequality bounding techniques, we derive for the first time the exact sample and time complexity upper bounds of the bit-by-bit guessing algorithm and the Gaussianelimination-based algebraic algorithm under a success probability of 1 − ε, thereby explicitly delineating the theoretical boundaries of classical algebraic attacks. On the quantum side, the central contribution of this paper is a novel polynomial system reduction method, Red2. This method equivalently transforms a nonlinear Boolean system of r equations and n variables into a 3sparse complex system whose constant terms are strictly −1, ensuring that the resulting Macaulay matrix satisfies the prerequisites for efficient quantum state preparation within O(TF − 2r) time. Building on this, we bridge the theoretical gap left by Ding et al. regarding unquantified reduction impacts, tightening the condition number lower degree D from  bound of a 1Macaulay  matrix of total   12 

2 D+h D+h − 12 Ω − 1 to Ω (T − 2r) , − 1 F h h and further extend the framework to Boolean Macaulay  1 −1 systems, decreasing the bound to Ω TF 2 (2h − 1) 2 . Nu-

18

(a)

(b)

FIG. 8. Time complexity of algorithms 2 and 4 with d = m. (a) h = log2 n. (b) h =

(a)

(b)

FIG. 9. Time complexity of algorithms 2 and 6 with d = m. (a) h = log2 n. (b) h =

merical instances constructed via an iterative optimization algorithm breach the theoretical limits established by Ding et al., empirically validating these tighter bounds. We further carry out a fine-grained logical-level evaluation of the quantum resources required by the proposed algorithms, deriving closed-form expressions for the circuit width, depth, and gate count. Since the circuit size scales as the square of the condition number, the compression of the condition number interval achieved by Red2 translates directly into a reduction in circuit depth and gate count, demonstrating that our improvement is not merely asymptotic but yields concrete, quantifiable resource savings. Applying the improved quantum algorithms to the LPSN problem exponentially reduces the

√ n.

√ n.

sample complexity; combined with 3D time complexity surfaces and an algorithm selection strategy, we show that √ even when h = Θ( n), the quantum algorithm retains the potential to outperform classical algorithms within specific parameter regimes. In summary, this research provides solid algorithmic and theoretical support for post-quantum algebraic cryptanalysis in sample-restricted scenarios. Future work may focus on quantum solving techniques that achieve optimal linear dependence on the condition number, such as the quantum singular value transformation, or explore heuristic quantum algorithms, such as the quantum approximate optimization algorithm, to solve nonlinear Boolean systems directly, thereby bypassing the linearization step.

19 ACKNOWLEDGMENTS

The authors gratefully acknowledge the support of the National Cryptologic Science Fund of China (Grant No. 2025NCSF02010). Appendix A: Structured Approximations for Low-Noise LPN Problems

Many restrictions on the noise within the LPN problem can be delineated using the LPSN framework. In fact, assuming the number of correlated noise variables is m, any structure within this set of samples that excludes at least one noise vector η can be represented by a nonzero polynomial. Below, we present three commonly utilized structured noise patterns, which approximate the low-noise-rate LPN problem with high probability. We exclusively provide a detailed analysis for the first structure; the analytical methodologies for the remaining two structures are perfectly analogous. Example A.1. Q Over GF(2), construct the polynomial P (η) = 1 ⊕ 1≤i<j≤m (1 ⊕ ηi ηj ). This polynomial over GF(2) satisfies the following property: when the Hamming weight of η (i.e., the number of components equal to 1) does not exceed 1, P (η) = 0; otherwise, P (η) = 1. The LPSN problem associated with the polynomial P is equivalent to imposing an additional constraint on the noise in the LPN problem, requiring that the Hamming weight of the vector formed by the noise across m samples is either 0 or 1. Intuitively, this corresponds to a special case of the LPN problem where the noise rate is 1 strictly less than m . However, the noise rate designates the expected probability that a noise bit is 1; in practice, the Hamming weight of the noise across m samples may exceed 1. By strictly forcing the noise in the m samples to conform to an acceptable noise pattern—that is, satisfying P (η) = 0—we eliminate the possibility of the noise’s Hamming weight exceeding 1, thereby guaranteeing that the Hamming weight of the noise within these m samples strictly does not exceed 1. Below, from a probabilistic perspective, we rigorously analyze the equivalence between the low-noise-rate LPN problem and the LPN problem

[1] M. Alekhnovich, More on average case vs approximation complexity, in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (IEEE, 2003) pp. 298–307. [2] A. Blum, M. Furst, M. Kearns, and R. J. Lipton, Cryptographic primitives based on hard learning problems, in Annual international cryptology conference (Springer, 1993) pp. 278–291. [3] N. J. Hopper and M. Blum, Secure human identification protocols, in International conference on the theory and application of cryptology and information security

under the aforementioned structured noise pattern. In the LPN problem with a noise rate of p, each sample independently contains noise with a probability of p. When we query the oracle Q(n, p, s) exactly m times, we obtain m independent samples. The probability that at most one of these samples contains noise is given by Pr[h(η) ≤ 1] = (1 − p)m + mp(1 − p)m−1 . We desire this probability to be sufficiently high to approximately simulate the LPSN oracle associated with the polynomial Q P (η) = 1 ⊕ 1≤i<j≤m (1 ⊕ ηi ηj ). Assuming m is suffi1 ciently large, when p = m , we have Pr[h(η) ≤ 1] ≈ 0.7358. This indicates that the m samples obtained via the LPN oracle Q can serve as the output samples of the LPSN oracle associated with the polynomial P with a probability of 0.7358. In fact, the LPSN problem associated with the polynomial P is equivalent to the LPN prob1 lem with a noise rate of p ≤ 10m with a probability of 0.9953. Naturally, the aforementioned high-probability equivalences consistently necessitate a substantially large number of correlated samples m. That is, when the correlation among sample noises is pronounced, algorithms designed for solving the LPSN problem can recover the secret vector in the LPN oracle corresponding to lower noise rates with a notably high success probability. Example A.2. Over GF(2), construct the polynomial  Pm  Q P (η) = 1 ⊕ i=1 ηi j̸=i (1 ⊕ ηj ) . This polynomial satisfies the property that P (η) = 0 if and only if the Hamming weight of η is exactly 1. This implies that the LPSN problem associated with the polynomial P demands that exactly one out of the m samples contains noise. Example A.3.
the polynomial Q Over GF(2), construct Q P (η) = 1 ⊕ S⊆[m],|S|=w+1 1 ⊕ i∈S ηi , where w satisfies 2w < m. This polynomial satisfies the property that P (η) = 0 if and only if the Hamming weight of η does not exceed w. This indicates that the LPSN problem associated with the polynomial P requires that at most w out of the m samples contain noise. It is straightforward to verify that the polynomials associated with the three structured noise patterns provided above all satisfy the requisite algebraic conditions.

(Springer, 2001) pp. 52–66. [4] G. Couteau, N. Kumar, and X. Ye, Multiparty homomorphic secret sharing and more from lpn and mq, in Theory of Cryptography Conference (Springer, 2025) pp. 498–530. [5] Z. Li, C. Xing, Y. Yao, and C. Yuan, Efficient pseudorandom correlation generators for any finite field, in Annual International Conference on the Theory and Applications of Cryptographic Techniques (Springer, 2025) pp. 145–175. [6] S. Arora and R. Ge, New algorithms for learning in presence of errors, in International Colloquium on Automata, Languages, and Programming (Springer, 2011) pp. 403–

20 415. [7] A. Blum, A. Kalai, and H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Journal of the ACM (JACM) 50, 506 (2003). [8] X. Wang and K. Sako, Advances in Cryptology– ASiACRYPT 2012: 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012, Proceedings, Vol. 7658 (Springer Science & Business Media, 2012). [9] A. Langlois, S. Ling, K. Nguyen, and H. Wang, Latticebased group signature scheme with verifier-local revocation, in International workshop on public key cryptography (Springer, 2014) pp. 345–361. [10] Y. Yu, J. Zhang, J. Weng, C. Guo, and X. Li, Collision resistant hashing from sub-exponential learning parity with noise, in International Conference on the Theory and Application of Cryptology and Information Security (Springer, 2019) pp. 3–24. [11] A. Author and B. Believer, A new unbreakable cryptosystem, Cryptology ePrint Archive, Paper 1990/001 (1990), https://eprint.iacr.org/1990/001. [12] L. Jiao, Specifications and improvements of lpn solving algorithms, IET Information Security 14, 111 (2020). [13] D. J. Bernstein, Grover vs. mceliece, in International Workshop on Post-Quantum Cryptography (Springer, 2010) pp. 73–80. [14] E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory 8, 5 (1962). [15] A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, in Annual International Conference on the Theory and Applications of Cryptographic Techniques (Springer, 2015) pp. 203–228. [16] G. Kachigar and J.-P. Tillich, Quantum information set decoding algorithms, in International Workshop on PostQuantum Cryptography (Springer, 2017) pp. 69–89. [17] B. Tran and S. Vaudenay, Solving the learning parity with noise problem using quantum algorithms, in International Conference on Cryptology in Africa (Springer, 2022) pp. 295–322. [18] G. Bard, Algebraic cryptanalysis (Springer Science & Business Media, 2009). [19] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical review letters 103, 150502 (2009). [20] A. Ambainis, Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations, arXiv preprint arXiv:1010.4458 (2010). [21] D. W. Berry, A. M. Childs, and R. Kothari, Hamiltonian simulation with nearly optimal dependence on all parameters, in 2015 IEEE 56th annual symposium on foundations of computer science (IEEE, 2015) pp. 792–809. [22] A. M. Childs, R. Kothari, and R. D. Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM Journal on Computing 46, 1920 (2017). [23] L. Wossnig, Z. Zhao, and A. Prakash, Quantum linear system algorithm for dense matrices, Physical review letters 120, 050502 (2018). [24] S. Chakraborty, A. Gilyén, and S. Jeffery, The power of block-encoded matrix powers: improved regression techniques via faster hamiltonian simulation, arXiv preprint arXiv:1804.01973 (2018).

[25] L. Lin and Y. Tong, Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems, Quantum 4, 361 (2020). [26] N. A. Nghiem, New quantum algorithm for solving linear system of equations, arXiv preprint arXiv:2502.13630 (2025). [27] A. Scherer, B. Valiron, S.-C. Mau, S. Alexander, E. Van den Berg, and T. E. Chapuran, Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2d target, Quantum Information Processing 16, 60 (2017). [28] Y.-A. Chen and X.-S. Gao, Quantum algorithm for boolean equation solving and quantum algebraic attack on cryptosystems, Journal of Systems Science and Complexity 35, 373 (2022). [29] J. Ding, V. Gheorghiu, A. Gilyén, S. Hallgren, and J. Li, Limitations of the macaulay matrix approach for using the hhl algorithm to solve multivariate polynomial systems, Quantum 7, 1069 (2023). [30] V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami, New results for learning noisy parities and halfspaces, in 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) (IEEE, 2006) pp. 563–574. [31] D. Aharonov and A. Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (2003) pp. 20–29. [32] V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami, On agnostic learning of parities, monomials, and halfspaces, SIAM Journal on Computing 39, 606 (2009). [33] G. Valiant, Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem, Journal of the ACM (JACM) 62, 1 (2015). [34] M. Karppa, P. Kaski, and J. Kohonen, A faster subquadratic algorithm for finding outlier correlations, ACM Transactions On Algorithms (TALG) 14, 1 (2018). [35] E. Grigorescu, L. Reyzin, and S. Vempala, On noisetolerant learning of sparse parities and related problems, in International Conference on Algorithmic Learning Theory (Springer, 2011) pp. 413–424. [36] B. Barak and A. Moitra, Noisy tensor completion via the sum-of-squares hierarchy, in Conference on Learning Theory (PMLR, 2016) pp. 417–445. [37] V. Guruswami, P. K. Kothari, and P. Manohar, Algorithms and certificates for boolean csp refutation: smoothed is no harder than random, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (2022) pp. 678–689. [38] B. Applebaum, B. Barak, and A. Wigderson, Public-key cryptography from different assumptions, in Proceedings of the forty-second ACM symposium on Theory of computing (2010) pp. 171–180. [39] B. Applebaum, Pseudorandom generators with long stretch and low locality from random local one-way functions, in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (2012) pp. 805–816. [40] A. Bogdanov, M. Sabin, and P. N. Vasudevan, Xor codes and sparse learning parity with noise, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2019) pp. 986–1004. [41] U. Feige, J. H. Kim, and E. Ofek, Witnesses for nonsatisfiability of dense random 3cnf formulas, in 2006 47th Annual IEEE Symposium on Foundations of Computer

21 Science (FOCS’06) (IEEE, 2006) pp. 497–508. [42] U. Feige, Small linear dependencies for binary vectors of low weight, in Building Bridges: Between Mathematics and Computer Science (Springer, 2008) pp. 283–307.

[43] X. Chen, W. Shu, and Z. Zhou, Algorithms for sparse lpn and lspn against low-noise, arXiv preprint arXiv:2407.19215 (2024).

Related documents

• Quantum Maximum Entropy Inference and Hamiltonian Learning#670287
• Quantum Maximum Entropy Inference and Hamiltonian Learning#668222
• Sharp Data-Processing Region for Quantum Conditional Rényi Entropies#1106049
• Distributing Quantum Computations, Shot-Wise#274736
• Improving ADMMs for solving doubly nonnegative programs through dual factorization#246996