FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodes

• URL: http://arxiv.org/abs/2210.17037v2
• Date: Tue, 4 Apr 2023 18:15:29 GMT
• Title: FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodes
• Authors: Ramin Ayanzadeh, Narges Alavisamani, Poulami Das, Moinuddin Qureshi
• Abstract summary: We propose FrozenQubits that freezes the hotspot nodes or qubits and intelligently partitions the state-space of the given problem into several smaller sub-spaces. Unlike prior circuit-cutting approaches, FrozenQubits does not require any exponentially complex post-processing step. Our evaluations with 5,300 QAOA circuits on eight different quantum computers from IBM shows that FrozenQubits can improve the quality of solutions by 8.73x on average.
• Score: 3.2505361717998227
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) is one of the leading candidates for demonstrating the quantum advantage using near-term quantum computers. Unfortunately, high device error rates limit us from reliably running QAOA circuits for problems with more than a few qubits. In QAOA, the problem graph is translated into a quantum circuit such that every edge corresponds to two 2-qubit CNOT operations in each layer of the circuit. As CNOTs are extremely error-prone, the fidelity of QAOA circuits is dictated by the number of edges in the problem graph. We observe that majority of graphs corresponding to real-world applications follow the ``power-law`` distribution, where some hotspot nodes have significantly higher number of connections. We leverage this insight and propose ``FrozenQubits`` that freezes the hotspot nodes or qubits and intelligently partitions the state-space of the given problem into several smaller sub-spaces which are then solved independently. The corresponding QAOA sub-circuits are significantly less vulnerable to gate and decoherence errors due to the reduced number of CNOT operations in each sub-circuit. Unlike prior circuit-cutting approaches, FrozenQubits does not require any exponentially complex post-processing step. Our evaluations with 5,300 QAOA circuits on eight different quantum computers from IBM shows that FrozenQubits can improve the quality of solutions by 8.73x on average (and by up to 57x), albeit utilizing 2x more quantum resources.

Related papers

• Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
  We propose an elaborate combination of two decomposition methods, namely graph shrinking and circuit cutting. Our results offer insights into the performance of algorithms for optimization problems within the constraints of current quantum technology.
  arXiv  Detail & Related papers  (2024-04-08T14:19:25Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Fast Flux-Activated Leakage Reduction for Superconducting Quantum Circuits [84.60542868688235]
  leakage out of the computational subspace arising from the multi-level structure of qubit implementations. We present a resource-efficient universal leakage reduction unit for superconducting qubits using parametric flux modulation. We demonstrate that using the leakage reduction unit in repeated weight-two stabilizer measurements reduces the total number of detected errors in a scalable fashion.
  arXiv  Detail & Related papers  (2023-09-13T16:21:32Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• The Complexity of Quantum Circuit Mapping with Fixed Parameters [4.716951747614208]
  A quantum circuit must be preprocessed before implementing on NISQ devices. Quantum circuit mapping transforms the circuit into an equivalent one that is compliant with the NISQ device's architecture constraint. We give an exact algorithm for QCM, and show that the algorithm runs in time if the NISQ device's architecture is fixed.
  arXiv  Detail & Related papers  (2022-07-18T08:44:45Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Shortcuts to Quantum Approximate Optimization Algorithm [2.150418646956503]
  We propose a new ansatz dubbed as "Shortcuts to QAOA" (S-QAOA) S-QAOA provides shortcuts to the ground state of target Hamiltonian by including more two-body interactions and releasing the parameter freedoms. Considering the MaxCut problem and Sherrington-Kirkpatrick (SK) model, numerically shows the YY interaction has the best performance.
  arXiv  Detail & Related papers  (2021-12-21T02:24:19Z)
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures [6.964575422457177]
  Connectivity of the physical qubits is one such constraint that restricts two-qubit operations, such as CNOT, to "connected" qubits. In this paper we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity constrained architectures. We "slice" the circuit at the position of Hadamard gates and "build" the intermediate CNOT,T sub-circuits using Steiner trees.
  arXiv  Detail & Related papers  (2020-11-24T16:35:05Z)
• 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)
• A QUBO Formulation for Qubit Allocation [0.0]
  present-day quantum computers have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.
  arXiv  Detail & Related papers  (2020-08-31T23:06:23Z)
• 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.