Studies of properties of bipartite graphs with quantum programming

Zohreh Davarzani, Mariam Zomorodi Moghadam, Mahboobeh Houshmand +1 more

Agnis Āriņš

Sebastian Dörn

Sovan Samanta

Xinjiang 新疆 Zhou 周, Tinggui Zhang

Abstract We establish a framework for constructing robust quantum-like states based on k -regular bipartite graphs, aiming to realize quantum-inspired information processing through classical oscillatory networks. We first introduce the k -regular bipartite graph and its mathematical representation, and analyze its intrinsic spectral properties. In contrast to ordinary k -regular non-bipartite graphs, the intrinsic bipartite symmetry, enhanced spectral gap, and global delocalization mechanism confer superior robustness to the emergent states. We verify that the emergent states of these bipartite graphs satisfy the axiomatic requirements of quantum-like states, and show that the global delocalization property ensures stable operation under structural noise. Based on the axiomatic requirements of quantum-like states, we further realize basic quantum-inspired gate operations in the classical network framework. Our numerical simulations reveal that the k -regular bipartite graph system exhibits enhanced coherence and stability under noise interference compared with non-bipartite graph systems. This research not only broadens the application boundaries of quantum-inspired computing but also provides a new feasible path for the practical implementation of classical simulation of quantum information processing.

Ben W. Reichardt, Robert Špalek

We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3-majority). The algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense. The main new tool is a correspondence between a classical linear-algebraic model of computation, “span programs,” and weighted bipartite graphs. A span program's evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph. A quantum computer can therefore evaluate the span program by applying spectral estimation to the graph. For example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization of randomized alpha-beta pruning is known to be suboptimal. In contrast, our algorithm generalizes the optimal quantum AND-OR formula evaluation algorithm and is optimal for evaluating the balanced ternary majority formula.