Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Implementation of a noise-robust quantum algorithm for multivariate polynomial factorization

Iñigo Perez Delgado, Lian-Ao Wu

Published Jul 18, 2022• 1 citation
Publisher

Abstract

We implement in an IBM quantum computer a quantum algorithm for multivariate polynomial factoring and propose a noise-avoiding protocol to distill the experimental results in the presence of noise. This algorithm uses single-qubit quantum state tomography (QST) processes to factor a specific type of multivariate polynomials. In one-to-one correspondence, it encodes each multivariate polynomial to one quantum state. While the validity of the algorithm is experimentally verified, the quality of the final results is subjected to the decoherence levels of the preparation of the quantum states. In this paper we propose a protocol to ensure the validity of factors found by our algorithm in the presence of such decoherence and noise. This method might be, in fact, part of a larger class of methods based on that same premise and useful outside the implementation of this specific algorithm. In combination with the noise robustness of the single-qubit QST, our factorization algorithm performs perfectly, even reversing the effects of weak noise, for the second- to fifth-order polynomial cases for which it has been implemented.

DOI
10.1103/physreva.106.012607

Related papers

Effects of noise on quantum error correction algorithms

Adriano Barenco, Todd A. Brun, Rüdiger Schack +1 more

It has recently been shown that there are efficient algorithms for quantum computers to solve certain problems, such as prime factorization, which are intractable to date on classical computers. The chances for practical implementation, however, are limited by decoherence, in which the effect of an external environment causes random errors in the quantum calculation. To combat this problem, quantum error correction schemes have been proposed, in which a single quantum bit (qubit) is ``encoded'' as a state of some larger number of qubits, chosen to resist particular types of errors. Most such schemes are vulnerable, however, to errors in the encoding and decoding itself. We examine two such schemes, in which a single qubit is encoded in a state of $n$ qubits while subject to dephasing or to arbitrary isotropic noise. Using both analytical and numerical calculations, we argue that error correction remains beneficial in the presence of weak noise, and that there is an optimal time between error correction steps, determined by the strength of the interaction with the environment and the parameters set by the encoding.

arXiv:quant-ph/9612047•Physical Review A•Aug 1, 1997•36 citations

Quantum State Tomography for Hardware Verification of Quantum Computers

Jincheng Zhang

Quantum state tomography (QST) is a fundamental technique for characterizing quantum states, traditionally employed in research laboratories with highly controlled environments. However, the burgeoning field of quantum computing faces the significant challenge of deploying and verifying quantum hardware in the presence of noise and decoherence, characteristics inherent in current Noisy Intermediate-Scale Quantum (NISQ) devices. This paper proposes an adapted QST algorithm designed to overcome these limitations. The core idea is to systematically reconstruct the density matrix of a qubit or a small quantum system using a series of carefully designed measurements. We address the impact of noise by incorporating error mitigation strategies within the reconstruction process. The algorithm's performance is evaluated through theoretical analysis and conceptual implementation, highlighting its potential to provide a practical and efficient method for hardware verification of NISQ computers. This work establishes a novel approach for characterizing and debugging NISQ hardware, a critical step toward realizing the full potential of quantum computation.

•Sep 6, 2026•0 citations

Polynomial time constructive decision algorithm for multivariable quantum signal processing

Yuki Ito, Hitomi Mori, Kazuki Sakamoto +1 more

Quantum signal processing (QSP) and quantum singular value transformation (QSVT) have provided a unified framework for understanding many quantum algorithms, including factorization, matrix inversion, and Hamiltonian simulation. As a multivariable version of QSP, multivariable quantum signal processing (M-QSP) is proposed. M-QSP interleaves signal operators corresponding to each variable with signal processing operators, which provides an efficient means to perform multivariable polynomial transformations. However, the necessary and sufficient condition for what types of polynomials can be constructed by M-QSP is unknown. In this paper, we propose a classical algorithm to determine whether a given pair of multivariable Laurent polynomials can be implemented by M-QSP, which returns True or False. As one of the most important properties of this algorithm, its returning True is the necessary and sufficient condition. The proposed classical algorithm runs in polynomial time in the number of variables and signal operators. Our algorithm also provides a constructive method to select the necessary parameters for implementing M-QSP. These findings offer valuable insights for identifying practical applications of M-QSP.

arXiv:2410.02332•Quantum•May 12, 2026•8 citations

Quantum error mitigation via quantum-noise-effect circuit groups

Yusuke Hama, Hirofumi Nishi

Near-term quantum computers have been built as intermediate-scale quantum devices and are fragile against quantum noise effects, namely, NISQ devices. Traditional quantum-error-correcting codes are not implemented on such devices and to perform quantum computation in good accuracy with these machines we need to develop alternative approaches for mitigating quantum computational errors. In this work, we propose quantum error mitigation (QEM) scheme for quantum computational errors which occur due to couplings with environments during gate operations, i.e., decoherence. To establish our QEM scheme, first we estimate the quantum noise effects on single-qubit states and represent them as groups of quantum circuits, namely, quantum-noise-effect circuit groups. Then our QEM scheme is conducted by subtracting expectation values generated by the quantum-noise-effect circuit groups from those obtained by the quantum circuits for the quantum algorithms under consideration. As a result, the quantum noise effects are reduced, and we obtain approximately the ideal expectation values via the quantum-noise-effect circuit groups and the numbers of elementary quantum circuits composing them scale polynomial with respect to the products of the depths of quantum algorithms and the numbers of register bits. To numerically demonstrate the validity of our QEM scheme, we run noisy quantum simulations of qubits under amplitude damping effects for four types of quantum algorithms. Furthermore, we implement our QEM scheme on IBM Q Experience processors and examine its efficacy. Consequently, the validity of our scheme is verified via both the quantum simulations and the quantum computations on the real quantum devices. Our QEM scheme is solely composed of quantum-computational operations (quantum gates and measurements), and thus, it can be conducted by any type of quantum device. In addition, it can be applied to error mitigation for many other types of quantum noise effects as well as noisy quantum computing of long-depth quantum algorithms.

arXiv:2205.13907•Scientific Reports•Mar 13, 2024•12 citations

Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach

Yuguo Shao, Fuchuan Wei, Song Cheng +1 more

Large-scale variational quantum algorithms are widely recognized as a potential pathway to achieve practical quantum advantages. However, the presence of quantum noise might suppress and undermine these advantages, which blurs the boundaries of classical simulability. To gain further clarity on this matter, we present a novel polynomial-scale method based on the path integral of observable's backpropagation on Pauli paths (OBPPP). This method efficiently approximates expectation values of operators in variational quantum algorithms with bounded truncation error in the presence of single-qubit Pauli noise. Theoretically, we rigorously prove: (i) For a constant minimal nonzero noise rate γ, OBPPP's time and space complexity exhibit a polynomial relationship with the number of qubits n, the circuit depth L. (ii) For variable γ, in scenarios where more than two nonzero noise factors exist, the complexity remains Poly(n,L) if γ exceeds 1/logL, but grows exponential with L when γ falls below 1/L. Numerically, we conduct classical simulations of IBM's zero-noise extrapolated experimental results on the 127-qubit Eagle processor [Y. Kim et al., Evidence for the utility of quantum computing before fault tolerance, Nature (London) 618, 500 (2023).NATUAS0028-083610.1038/s41586-023-06096-3]. Our method attains higher accuracy and faster runtime compared to the quantum device. Furthermore, our approach allows us to simulate noisy outcomes, enabling accurate reproduction of IBM's unmitigated results that directly correspond to raw experimental observations. Our research reveals the vital role of noise in classical simulations and the derived method is general in computing the expected value for a broad class of quantum circuits and can be applied in the verification of quantum computers.

arXiv:2306.05804•Physical Review Letters•Sep 18, 2024•53 citations

On variants of multivariate quantum signal processing and their characterizations

Németh, Balázs, Blanka Kövér, Boglárka Kulcsár +2 more

Quantum signal processing (QSP) is a highly successful algorithmic primitive in quantum computing which leads to conceptually simple and efficient quantum algorithms using the block-encoding framework of quantum linear algebra. Multivariate variants of quantum signal processing (MQSP) could be a valuable tool in extending earlier results via implementing multivariate (matrix) polynomials. However, MQSP remains much less understood than its single-variate version lacking a clear characterization of "achievable" multivariate polynomials. We show that Haah's characterization of general univariate QSP can be extended to homogeneous bivariate (commuting) quantum signal processing. We also show a similar result for an alternative inhomogeneous variant when the degree in one of the variables is at most 1, but construct a counterexample where both variables have degree 2, which in turn refutes an earlier characterization proposed / conjectured by Rossi and Chuang for a related restricted class of MQSP. Finally, we describe homogeneous multivariate (non-commuting) QSP variants that break away from the earlier two-dimensional treatment limited by its reliance on Jordan-like decompositions, and might ultimately lead to the development of novel quantum algorithms.

arXiv:2312.09072•Dec 14, 2023•31 citations
We implement in an IBM quantum computer a quantum algorithm for multivariate polynomial factoring and propose a noise-avoiding protocol to distill the experimental results in the presence of noise. This algorithm uses single-qubit quantum state tomography (QST) processes to factor a specific type of multivariate polynomials. In one-to-one correspondence, it encodes each multivariate polynomial to one quantum state. While the validity of the algorithm is experimentally verified, the quality of the final results is subjected to the decoherence levels of the preparation of the quantum states. In this paper we propose a protocol to ensure the validity of factors found by our algorithm in the presence of such decoherence and noise. This method might be, in fact, part of a larger class of methods based on that same premise and useful outside the implementation of this specific algorithm. In combination with the noise robustness of the single-qubit QST, our factorization algorithm performs perfectly, even reversing the effects of weak noise, for the second- to fifth-order polynomial cases for which it has been implemented.
It has recently been shown that there are efficient algorithms for quantum computers to solve certain problems, such as prime factorization, which are intractable to date on classical computers. The chances for practical implementation, however, are limited by decoherence, in which the effect of an external environment causes random errors in the quantum calculation. To combat this problem, quantum error correction schemes have been proposed, in which a single quantum bit (qubit) is ``encoded'' as a state of some larger number of qubits, chosen to resist particular types of errors. Most such schemes are vulnerable, however, to errors in the encoding and decoding itself. We examine two such schemes, in which a single qubit is encoded in a state of nnn qubits while subject to dephasing or to arbitrary isotropic noise. Using both analytical and numerical calculations, we argue that error correction remains beneficial in the presence of weak noise, and that there is an optimal time between error correction steps, determined by the strength of the interaction with the environment and the parameters set by the encoding.
Quantum state tomography (QST) is a fundamental technique for characterizing quantum states, traditionally employed in research laboratories with highly controlled environments. However, the burgeoning field of quantum computing faces the significant challenge of deploying and verifying quantum hardware in the presence of noise and decoherence, characteristics inherent in current Noisy Intermediate-Scale Quantum (NISQ) devices. This paper proposes an adapted QST algorithm designed to overcome these limitations. The core idea is to systematically reconstruct the density matrix of a qubit or a small quantum system using a series of carefully designed measurements. We address the impact of noise by incorporating error mitigation strategies within the reconstruction process. The algorithm's performance is evaluated through theoretical analysis and conceptual implementation, highlighting its potential to provide a practical and efficient method for hardware verification of NISQ computers. This work establishes a novel approach for characterizing and debugging NISQ hardware, a critical step toward realizing the full potential of quantum computation.
Quantum signal processing (QSP) and quantum singular value transformation (QSVT) have provided a unified framework for understanding many quantum algorithms, including factorization, matrix inversion, and Hamiltonian simulation. As a multivariable version of QSP, multivariable quantum signal processing (M-QSP) is proposed. M-QSP interleaves signal operators corresponding to each variable with signal processing operators, which provides an efficient means to perform multivariable polynomial transformations. However, the necessary and sufficient condition for what types of polynomials can be constructed by M-QSP is unknown. In this paper, we propose a classical algorithm to determine whether a given pair of multivariable Laurent polynomials can be implemented by M-QSP, which returns True or False. As one of the most important properties of this algorithm, its returning True is the necessary and sufficient condition. The proposed classical algorithm runs in polynomial time in the number of variables and signal operators. Our algorithm also provides a constructive method to select the necessary parameters for implementing M-QSP. These findings offer valuable insights for identifying practical applications of M-QSP.
Near-term quantum computers have been built as intermediate-scale quantum devices and are fragile against quantum noise effects, namely, NISQ devices. Traditional quantum-error-correcting codes are not implemented on such devices and to perform quantum computation in good accuracy with these machines we need to develop alternative approaches for mitigating quantum computational errors. In this work, we propose quantum error mitigation (QEM) scheme for quantum computational errors which occur due to couplings with environments during gate operations, i.e., decoherence. To establish our QEM scheme, first we estimate the quantum noise effects on single-qubit states and represent them as groups of quantum circuits, namely, quantum-noise-effect circuit groups. Then our QEM scheme is conducted by subtracting expectation values generated by the quantum-noise-effect circuit groups from those obtained by the quantum circuits for the quantum algorithms under consideration. As a result, the quantum noise effects are reduced, and we obtain approximately the ideal expectation values via the quantum-noise-effect circuit groups and the numbers of elementary quantum circuits composing them scale polynomial with respect to the products of the depths of quantum algorithms and the numbers of register bits. To numerically demonstrate the validity of our QEM scheme, we run noisy quantum simulations of qubits under amplitude damping effects for four types of quantum algorithms. Furthermore, we implement our QEM scheme on IBM Q Experience processors and examine its efficacy. Consequently, the validity of our scheme is verified via both the quantum simulations and the quantum computations on the real quantum devices. Our QEM scheme is solely composed of quantum-computational operations (quantum gates and measurements), and thus, it can be conducted by any type of quantum device. In addition, it can be applied to error mitigation for many other types of quantum noise effects as well as noisy quantum computing of long-depth quantum algorithms.
Large-scale variational quantum algorithms are widely recognized as a potential pathway to achieve practical quantum advantages. However, the presence of quantum noise might suppress and undermine these advantages, which blurs the boundaries of classical simulability. To gain further clarity on this matter, we present a novel polynomial-scale method based on the path integral of observable's backpropagation on Pauli paths (OBPPP). This method efficiently approximates expectation values of operators in variational quantum algorithms with bounded truncation error in the presence of single-qubit Pauli noise. Theoretically, we rigorously prove: (i) For a constant minimal nonzero noise rate γ, OBPPP's time and space complexity exhibit a polynomial relationship with the number of qubits n, the circuit depth L. (ii) For variable γ, in scenarios where more than two nonzero noise factors exist, the complexity remains Poly(n,L) if γ exceeds 1/logL, but grows exponential with L when γ falls below 1/L. Numerically, we conduct classical simulations of IBM's zero-noise extrapolated experimental results on the 127-qubit Eagle processor [Y. Kim et al., Evidence for the utility of quantum computing before fault tolerance, Nature (London) 618, 500 (2023).NATUAS0028-083610.1038/s41586-023-06096-3]. Our method attains higher accuracy and faster runtime compared to the quantum device. Furthermore, our approach allows us to simulate noisy outcomes, enabling accurate reproduction of IBM's unmitigated results that directly correspond to raw experimental observations. Our research reveals the vital role of noise in classical simulations and the derived method is general in computing the expected value for a broad class of quantum circuits and can be applied in the verification of quantum computers.
Quantum signal processing (QSP) is a highly successful algorithmic primitive in quantum computing which leads to conceptually simple and efficient quantum algorithms using the block-encoding framework of quantum linear algebra. Multivariate variants of quantum signal processing (MQSP) could be a valuable tool in extending earlier results via implementing multivariate (matrix) polynomials. However, MQSP remains much less understood than its single-variate version lacking a clear characterization of "achievable" multivariate polynomials. We show that Haah's characterization of general univariate QSP can be extended to homogeneous bivariate (commuting) quantum signal processing. We also show a similar result for an alternative inhomogeneous variant when the degree in one of the variables is at most 1, but construct a counterexample where both variables have degree 2, which in turn refutes an earlier characterization proposed / conjectured by Rossi and Chuang for a related restricted class of MQSP. Finally, we describe homogeneous multivariate (non-commuting) QSP variants that break away from the earlier two-dimensional treatment limited by its reliance on Jordan-like decompositions, and might ultimately lead to the development of novel quantum algorithms.