Tutorial: implement ADAPT-Clifford algorithm for MaxCut problem

[Fe-r-oz]

Is your feature request related to a problem? Please describe.

Hi, @manuelmz, pinged you as this is directly related to your work. Please feel free to provide further insights.

Muñoz-Arias et al. show that low-depth Clifford circuits can approximate solutions to MaxCut, introducing the quantum-inspired algorithm ADAPT-Clifford for this purpose. This algorithm approximates MaxCut on an N-vertex weighted fully connected graph by constructing a depth O(N) Clifford circuit with runtime complexity O(N²) for sparse graphs and O(N³) for dense graphs, while maintaining space complexity of O(N²). The above run-times are for the 'randomized' variant of the ADAPT-Clifford. For the 'deterministic' variant, the metrics are runtime complexity O(N³) for sparse graphs and O(N⁴) for dense graphs.

The key insight is that ADAPT-QAOA 'solution unitaries' for MaxCut closely approximate Clifford circuits. This algorithm was implemented in stim. To understand the origin of ADAPT-Clifford, review the solution circuits from QAOA and ADAPT-QAOA applied to small weighted complete graphs. Utilize Yao.jl's QuAlgorithmZoo for variational algorithms with the COBYLA optimizer, and analyze operator distribution in the Pauli basis using QuantumOptics.jl.

Describe the solution you’d like

Make a tutorial about using QuantumClifford for implementing the ADAPT-Clifford algorithm for the MaxCut problem. For reference, check out Manual's stim-based implementation: ADAPT-Clifford. Also, compare the performance of the implemented algorithm with stim-based implementation.

The best known classical approximation algorithm with good guarantee is Goemans-Williamson (GW) which has been used by Manual for comparison with ADAPT-Clifford. GW algorithm is present in QuAlgorithmZoo . This tutorial would be an nice demonstration of solving combinatorial optimization problems using the approximate Clifford algorithm.

Describe alternatives you’ve considered

To be added soon.

Additional context

Manuel notes that ADAPT-Clifford could be implemented by any stabilizer circuit simulator given that the two conditions are met: 1) Given it computes Pauli string expectation values 2) allows 'circuit modification' based on the results.