Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations

被引：4

作者：

Sano, Yuki ^{[1
]}

Mitarai, Kosuke ^{[2
]}

Yamamoto, Naoki ^{[3
]}

Ishikawa, Naoki ^{[1
,3
]}

机构：

[1] Yokohama Natl Univ, Fac Engn, Yokohama 2408501, Japan

[2] Osaka Univ, Grad Sch Engn Sci, Toyonaka 5600043, Japan

[3] Keio Univ, Dept Appl Phys & Physico Informat, Kohoku 2238522, Japan

来源：

IEEE TRANSACTIONS ON QUANTUM ENGINEERING | 2024年 / 5卷

基金：

日本学术振兴会; 日本科学技术振兴机构;

关键词：

Qubit; Logic gates; Optimization; Quantum computing; Encoding; Vectors; Urban areas; Graph coloring problem (GCP); Grover adaptive search (GAS); higher order unconstrained binary optimization (HUBO); quadratic unconstrained binary optimization (QUBO); traveling salesman problem (TSP); COHERENT ISING MACHINE; OPTIMIZATION;

D O I：

10.1109/TQE.2024.3393437

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. In this article, we propose higher order binary formulations that can simultaneously reduce the numbers of qubits and gates required for GAS. Specifically, we consider two novel strategies: one that reduces the number of gates through polynomial factorization, and the other that halves the order of the objective function, subsequently decreasing circuit runtime and implementation cost. Our analysis demonstrates that the proposed higher order formulations improve the convergence performance of GAS by reducing both the search space size and the number of quantum gates. Our strategies are also beneficial for general combinatorial optimization problems using one-hot encoding.

引用

页码：1 / 12

页数：12