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.
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.
Recently Chen and Gao \cite{ChenGao2017} proposed a new quantum algorithm for Boolean polynomial system solving, motivated by the cryptanalysis of some post-quantum cryptosystems. The key idea of their approach is to apply a Quantum Linear System (QLS) algorithm to a Macaulay linear system over C , which is derived from the Boolean polynomial system. The efficiency of their algorithm depends on the condition number of the Macaulay matrix. In this paper, we give a strong lower bound on the condition number as a function of the Hamming weight of the Boolean solution, and show that in many (if not all) cases a Grover-based exhaustive search algorithm outperforms their algorithm. Then, we improve upon Chen and Gao's algorithm by introducing the Boolean Macaulay linear system over C by reducing the original Macaulay linear system. This improved algorithm could potentially significantly outperform the brute-force algorithm, when the Hamming weight of the solution is logarithmic in the number of Boolean variables.Furthermore, we provide a simple and more elementary proof of correctness for our improved algorithm using a reduction employing the Valiant-Vazirani affine hashing method, and also extend the result to polynomial systems over Fq improving on subsequent work by Chen, Gao and Yuan \citeChenGao2018. We also suggest a new approach for extracting the solution of the Boolean polynomial system via a generalization of the quantum coupon collector problem \cite{arunachalam2020QuantumCouponCollector}.
Abstract Noisy linear problems have been studied in various science and engineering disciplines. A class of ‘hard’ noisy linear problems can be formulated as follows: Given a matrix A ^ and a vector b constructed using a finite set of samples, a hidden vector or structure involved in b is obtained by solving a noise-corrupted linear equation A ^ x ≈ b + η , where η is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.
Quantum resources can dramatically reduce the data required to learn physical systems, with exponential improvements in sample complexity demonstrated in several quantum learning tasks. However, these advantages have typically relied on quantum resources that scale with problem complexity, most notably increasing system dimension or entanglement. This raises a fundamental question: can exponential quantum learning advantages arise within a fixed, unentangled quantum system? In this paper, we address this question by considering the learning of an unknown random-displacement distribution whose complexity is determined not by the dimensionality of the physical system, but by the Fourier resolution of its features. We show that the quantum-limited noise of vacuum probes progressively obscures high-frequency features, leading to an exponential growth in sample complexity. We establish an information-theoretic lower bound for arbitrary classical-state probes and show that squeezing overcomes this classical limit by extending the accessible Fourier bandwidth. Experimentally, we demonstrate an exponential reduction in sample complexity using squeezed vacuum probes for both binary hypothesis testing and characteristic-function reconstruction. Our results show that a single bosonic mode can exhibit exponential quantum learning advantages without entanglement or an increase in system size, identifying accessible Fourier bandwidth as a fundamentally distinct resource for quantum-enhanced learning.
Abstract The main promise of quantum computing is to efficiently solve certain problems that are prohibitively expensive for a classical computer. Most problems with a proven quantum advantage involve the repeated use of a black box, or oracle, whose structure encodes the solution. One measure of the algorithmic performance is the query complexity, i.e., the scaling of the number of oracle calls needed to find the solution with a given probability. Few-qubit demonstrations of quantum algorithms, such as Deutsch–Jozsa and Grover, have been implemented across diverse physical systems such as nuclear magnetic resonance, trapped ions, optical systems, and superconducting circuits. However, at the small scale, these problems can already be solved classically with a few oracle queries, limiting the obtained advantage. Here we solve an oracle-based problem, known as learning parity with noise, on a five-qubit superconducting processor. Executing classical and quantum algorithms using the same oracle, we observe a large gap in query count in favor of quantum processing. We find that this gap grows by orders of magnitude as a function of the error rates and the problem size. This result demonstrates that, while complex fault-tolerant architectures will be required for universal quantum computing, a significant quantum advantage already emerges in existing noisy systems.
Preconditioning is a fundamental technique for accelerating classical linear system solvers, and understanding when its benefits persist in quantum linear system (QLS) solvers is important for assessing the practical resource requirements of quantum linear algebra. In QLS algorithms, however, the potential advantage of preconditioning may be offset by the normalization overhead incurred by composing separate block-encodings of the system matrix and the preconditioner, as observed in recent work. This limitation leaves open whether additional algebraic structure can make preconditioning effective in quantum access models. Motivated by this question, we show that Pauli-structured representations of both the system matrix and the preconditioner allow the preconditioned operator to be accessed through regrouped Pauli expansions. In this setting, algebraic regrouping of Pauli products can reduce the Pauli coefficient weight of the preconditioned operator, thereby altering the normalization parameters relevant to quantum algorithms. We derive explicit size and coefficient-weight bounds for the regrouped Pauli representations, and we trace their consequences for both direct block-encoding constructions and randomized Pauli linear system solvers. These results identify when Pauli-structured preconditioning can reduce the effective complexity parameters of QLS algorithms, rather than merely improving the classical condition number. Numerical experiments on a finite-dimensional synthetic benchmark show reductions in norm-aware direct block-encoding diagnostics and in the randomized QLS per-sample depth proxy.
Noisy linear problems have been studied in various science and engineering disciplines. A class of hard noisy linear problems can be formulated as follows: Given a matrix A^ and a vector b constructed using a finite set of samples, a hidden vector or structure involved in b is obtained by solving a noise-corrupted linear equation A^x≈b+η, where η is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.