The Quantum Alternating Operator Ansatz (QAOA+) framework has recently gained attention due to its ability to solve discrete optimization problems on noisy intermediate-scale quantum (NISQ) devices in a manner that is amenable to derivation of worst-case guarantees. We design a technique in this framework to tackle a few problems over maximal matchings in graphs. Even though maximum matching is polynomial-time solvable, most counting and sampling versions are #P-hard. We design a few algorithms that generates superpositions over matchings allowing us to sample from them. In particular, we get a superposition over all possible matchings when given the empty state as input and a superposition over all maximal matchings when given the W -states as input. Our main result is that the expected size of the matchings corresponding to the output states of our QAOA+ algorithm when ran on a 2-regular graph is greater than the expected matching size obtained from a uniform distribution over all matchings. This algorithm uses a W -state as input and we prove that this input state is better compared to using the empty matching as the input state.

翻译：QAOA+ (QAOA+) 的量子替代操作操作器 Ansatz (QAOA+) 框架最近因其能以最坏的保证衍生出的方式解决超声中间量设备离散优化问题而引起关注。 我们在这个框架中设计了一种技术来解决图表中最大匹配方面的几个问题。 尽管最大匹配是多元时间可溶的, 但大多数计数和抽样版本都是 # P- 硬 。 我们设计了几种算法, 产生比对匹配的比对, 从而允许我们从中提取样本。 特别是, 当给以空状态作为输入时, 我们得到所有可能的匹配的比对最大匹配的比对, 当给以W - 状态作为输入时, 我们得到所有最大匹配的比对最大匹配的比对。 我们的主要结果是, 与我们 QAOA+ 算法输出状态相对的预期匹配大小大于从所有匹配的统一分布中获得的预期匹配大小。 这个算法使用 W - state 作为输入, 我们证明这个输入状态比使用空匹配输入的比空匹配要好。