Noisy Quantum Circuits Simulated Faster

Researchers at the University of New Mexico have developed a new algorithm accurately simulating the behaviour of noisy quantum computers. Shravan and colleagues present a polynomial-time classical algorithm capable of sampling output distributions from instantaneous quantum polynomial (IQP) circuits affected by amplitude-damping noise. The algorithm addresses a key gap in the field, as most existing simulation techniques rely on specific types of noise or inherent randomness, whereas this one functions effectively with non-unital noise and without requiring randomness. Efficient simulation of these circuits, generated by arbitrary local gates with sufficient depth, is a vital step towards validating quantum computations and developing strong error mitigation strategies for near-term quantum devices.

Polynomial time simulation of amplitude-damped instantaneous quantum polynomial circuits overcomes existing limitations

Circuits previously requiring a depth exceeding Ω(log(n)) for classical simulation are now efficiently sampled in polynomial time. The breakthrough applies to amplitude-damped instantaneous quantum polynomial (IQP) circuits, a class specifically designed to challenge classical computers and benchmark quantum supremacy. These circuits are constructed using Clifford gates and a non-Clifford gate, typically a Hadamard gate applied to a specific qubit, creating a computational basis state that is difficult for classical computers to represent efficiently. Previous methods struggled with circuits beyond this logarithmic depth or relied on specific noise conditions, such as unital noise where the trace of the noise operator is preserved, meaning the overall probability remains constant. Researchers have developed a classical algorithm capable of simulating quantum circuits previously considered beyond reach, utilising arbitrary ‘l-local diagonal gates’, meaning gates acting on a limited number of qubits at a time. Diagonal gates, in this context, represent operations that preserve the diagonal elements of the density matrix, simplifying the simulation process. This expands the scope of verifiable quantum computation and offers a new tool for developing error mitigation techniques, enabling the investigation of more complex quantum behaviours. The ability to efficiently simulate these circuits allows for rigorous testing of quantum algorithms and hardware before deployment on actual quantum devices, reducing the risk of errors and improving overall performance. The algorithm’s efficiency stems from a novel approach to tracking the evolution of the quantum state under the influence of both the unitary gates and the amplitude-damping noise, effectively reducing the computational complexity.

Idle circuits expose limitations in classical simulation of quantum dynamics

Classical simulation of quantum circuits provides a vital means of verifying designs and mitigating errors as practical quantum computation approaches. However, this work reveals a curious limitation; the algorithm’s performance appears weakest when simulating the simplest possible scenario: an idle circuit consisting solely of noise. An idle circuit, in this case, represents a quantum system subjected only to the amplitude-damping noise without any gate operations. This suggests a subtle interaction between circuit complexity and the algorithm’s efficiency, hinting that even minimal quantum operations can paradoxically ease the computational burden. The reason for this behaviour is not fully understood, but it is theorised that the absence of coherent evolution introduced by the unitary gates hinders the algorithm’s ability to efficiently track the state’s evolution. The algorithm relies on certain patterns emerging from the interplay between unitary operations and noise, and these patterns are absent in a purely noisy system. This finding challenges the intuitive notion that simpler circuits should always be easier to simulate and highlights the importance of considering the specific characteristics of both the circuit and the noise model.

Further investigation into the interplay between noise characteristics and circuit structure is prompted by the algorithm’s struggle with idle circuits, potentially guiding the development of more robust simulation techniques. Understanding why the algorithm falters on idle circuits could lead to modifications that improve its performance across a wider range of scenarios. The development of algorithms capable of efficiently simulating quantum circuits remains significant despite this subtle finding. A polynomial-time classical algorithm for simulating circuits affected by amplitude-damping noise has been established, representing a common error type in real quantum devices. Amplitude-damping noise arises from the spontaneous emission of photons from qubits, leading to a loss of quantum information and decoherence. This work establishes a pathway for classically simulating a specific type of noisy quantum computation, instantaneous quantum polynomial (IQP) circuits, utilising diagonal gates subject to amplitude-damping noise, which represents the loss of energy from excited quantum states. Achieving polynomial-time simulation for circuits with a depth of Ω(log(n)) bypasses limitations previously hindering classical verification of these systems. The implications extend to the validation of quantum algorithms designed to run on near-term intermediate-scale quantum (NISQ) devices, where noise is a significant challenge. By providing a means to accurately simulate the effects of amplitude-damping noise, researchers can better understand and mitigate errors in these devices, paving the way for more reliable quantum computations. The algorithm’s efficiency opens up possibilities for exploring larger and more complex quantum circuits than previously feasible, accelerating the development of quantum technologies.

The researchers developed a classical algorithm capable of simulating noisy quantum circuits in polynomial time. This is significant because accurately simulating quantum computations is crucial for verifying quantum algorithms on near-term devices, where noise is a major problem. The algorithm successfully samples output distributions from instantaneous quantum polynomial circuits with diagonal gates, affected by constant amplitude-damping noise and a depth of Ω(log(n)). The authors suggest further research should focus on understanding why the algorithm struggles with idle circuits to improve its overall performance.