论文标题
超越产品状态近似值的最大量子类似物
Beyond product state approximations for a quantum analogue of Max Cut
论文作者
论文摘要
我们考虑了一个计算问题，其目标是近似于两个局部哈密顿量的最大特征值，该量子描述了位于图形顶点的Qubits之间的Heisenberg相互作用。以前的工作已经阐明了该问题的近似性。对于此问题的任何实例，产品状态获得的最大能量均受图形的最大切割和上限，并受到标准的goemans-williamson Semidefinite Smagihite编程的限制。 Gharibian和Parekh描述了该问题有效的经典近似算法，该算法在最坏的情况下输出具有能量的最大特征值的0.498倍的产品状态，并观察到存在最佳产品状态的实例具有最佳能量1/2的最佳能量。我们研究了近似算法，其性能超过了此限制，该算法基于对少量状态和浅量子电路的张量产品的优化。我们提供了一种有效的经典算法，在最坏情况下，达到至少0.53的近似值。我们还表明，对于由3或4型图定义的任何实例，都有一个有效计算的浅量子电路，该状态的能量具有大于最佳产品状态的能量（甚至比其半决赛编程松弛更大）。
We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problem's approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3- or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).
