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

• URL: http://arxiv.org/abs/2308.01572v2
• Date: Sun, 12 May 2024 23:06:30 GMT
• Title: Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
• Authors: Yuki Sano, Kosuke Mitarai, Naoki Yamamoto, Naoki Ishikawa,
• Abstract summary: Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. We propose higher-order binary formulations that can simultaneously reduce the numbers of qubits and required gates.
• Score: 2.9564164925541503
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. In this paper, 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 both reducing the search space size and the number of quantum gates. Our strategies are also beneficial for general combinatorial optimization problems using one-hot encoding.

Related papers

• Quantum Speedup for the Quadratic Assignment Problem [6.106029308649016]
  We show that the search space of the quadratic assignment problem can be reduced using Grover adaptive search (GAS) with Dicke state operators. We also show that the phase gate in the GAS can be replaced by a rotation gate about the Z axis, simplifying the quantum circuit without any penalty.
  arXiv  Detail & Related papers  (2024-10-16T03:00:37Z)
• Grover Adaptive Search with Spin Variables [3.190355298836875]
  We introduce a novel quantum dictionary subroutine that is designed for this spin-based algorithm. A key benefit of this approach is the substantial reduction in the number of CNOT gates required to construct the quantum circuit.
  arXiv  Detail & Related papers  (2024-10-15T14:24:27Z)
• Quantum Speedup of the Dispersion and Codebook Design Problems [6.735173690339397]
  Dispersion problems are optimization problems classified as NP-hard. We propose new formulations of max-sum and max-min dispersion problems that enable solutions via the Grover adaptive search (GAS) quantum algorithm.
  arXiv  Detail & Related papers  (2024-06-11T12:00:50Z)
• Optimizing Variational Circuits for Higher-Order Binary Optimization [2.578242050187029]
  We propose new approaches to encode their Hamiltonian into a ready-to-implement circuit involving only two-qubit gates. We evaluate our approaches by comparing them with the state of the art, showcasing clear gains in terms of circuit depth.
  arXiv  Detail & Related papers  (2023-07-31T15:27:06Z)
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem [2.840363325289377]
  We propose a novel method of formulating an NP-hard wireless channel assignment problem as a higher-order unconstrained binary optimization (HUBO) We conceive ascending and descending binary encodings of the channel indices, construct a specific quantum circuit, and derive the exact numbers of qubits and gates required by Grover adaptive search (GAS) Our analysis clarifies that the proposed HUBO formulation significantly reduces the number of qubits and the query complexity compared with the conventional quadratic formulation.
  arXiv  Detail & Related papers  (2022-08-10T06:59:43Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.