Benchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative

We study the performance scaling of three quantum algorithms for combinatorial optimization: measurement-feedback coherent Ising machines (MFB-CIM), discrete adiabatic quantum computation (DAQC), and the Durr-Hoyer algorithm for quantum minimum finding (DH-QMF) that is based on Grovers search. We use MaxCut problems as our reference for comparison, and time-to-solution (TTS) as a practical measure of performance for these optimization algorithms. We empirically observe a $Theta(2^{sqrt{n}})$ scaling for the median TTS for MFB-CIM, in comparison to the exponential scaling with the exponent $n$ for DAQC and the provable $widetilde{mathcal O}left(sqrt{2^n}right)$ scaling for DH-QMF. We conclude that these scaling complexities result in a dramatic performance advantage for MFB-CIM in comparison to the other two algorithms for solving MaxCut problems.

On the $C_p$-equivariant dual Steenrod algebra

We compute the $C_p$-equivariant dual Steenrod algebras associated to the constant Mackey functors $underline{mathbb{F}}_p$ and $underline{mathbb{Z}}_{(p)}$, as $underline{mathbb{Z}}_{(p)}$-modules. The $C_p$-spectrum $underline{mathbb{F}}_p otimes underline{mathbb{F}}_p$ is not a direct sum of $RO(C_p)$-graded suspensions of $underline{mathbb{F}}_p$ when $p$ is odd, in contrast with the classical and $C_2$-equivariant dual Steenrod algebras.