Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach.

Area of Science:

• Quantum Computing
• Computational Complexity
• Quantum Information Science

Background:

• Large-scale variational quantum algorithms (VQAs) promise practical quantum advantage.
• Quantum noise challenges VQAs and blurs classical simulation boundaries.
• Accurate simulation of noisy VQAs is crucial for understanding quantum advantage.

Purpose of the Study:

• To develop a novel, efficient method for approximating expectation values in noisy VQAs.
• To analyze the computational complexity of the proposed method under different noise conditions.
• To validate the method's performance against experimental quantum computing results.

Main Methods:

• Introduced the observable's backpropagation on Pauli paths (OBPPP), a polynomial-scale method.
• Theoretically analyzed OBPPP's time and space complexity with respect to qubit count (n) and circuit depth (L).
• Conducted classical simulations of experimental VQA results, including noisy outcome reproduction.

Main Results:

• OBPPP efficiently approximates expectation values in VQAs with bounded truncation error under single-qubit Pauli noise.
• OBPPP exhibits polynomial complexity Poly(n,L) for constant noise rates and certain variable noise scenarios.
• Simulations showed OBPPP achieved higher accuracy and faster runtime than the quantum device, reproducing experimental noisy results.

Conclusions:

• The OBPPP method provides a robust tool for simulating noisy VQAs, revealing noise's critical role in classical simulations.
• OBPPP's complexity is polynomial under specific noise conditions, offering a scalable simulation approach.
• The method is general for various quantum circuits and applicable to quantum computer verification.