Efficient Classical Simulation of Clifford Circuits with Nonstabilizer Input States.

Area of Science:

• Quantum Computing
• Computational Complexity
• Quantum Information Theory

Background:

• Evaluating output probabilities of Clifford circuits is crucial for quantum computation.
• Nonstabilizer product states pose a computational challenge in Clifford circuit analysis.
• Existing methods struggle with the complexity introduced by nonstabilizer inputs.

Purpose of the Study:

• To develop efficient classical algorithms for approximating Clifford circuit output probabilities with nonstabilizer product input states.
• To analyze the performance of these algorithms based on input state properties (mixedness, purity) and measurement restrictions.
• To explore the role of Pauli rank as a resource for efficient computation.

Main Methods:

• Development of a classical approximation algorithm for mixed nonstabilizer product states, analyzed using the l1 norm.
• Design of a similar approximation algorithm for pure nonstabilizer product states, contingent on qubit measurement restrictions.
• Introduction and utilization of the 'Pauli rank' as a magic monotone to define computational restrictions.

Main Results:

• An efficient classical algorithm approximates output probabilities for a significant fraction of Clifford circuits with mixed nonstabilizer inputs.
• Algorithm efficiency increases with input state mixedness.
• An efficient algorithm is demonstrated for pure nonstabilizer states under Pauli rank-dependent measurement restrictions.

Conclusions:

• Efficient approximation of Clifford circuit output probabilities is achievable even with nonstabilizer inputs under specific conditions.
• Pauli rank is a key resource for enabling efficient quantum computation in restricted models.
• The findings provide insights into the computational power and limitations of various quantum computing models.