Scaling Quantum Approximate Optimization on Near-term Hardware
- URL: http://arxiv.org/abs/2201.02247v1
- Date: Thu, 6 Jan 2022 21:02:30 GMT
- Title: Scaling Quantum Approximate Optimization on Near-term Hardware
- Authors: Phillip C. Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey,
Rebekah Herrman, James Ostrowski, George Siopsis, and Travis S. Humble
- Abstract summary: We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
- Score: 49.94954584453379
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is an approach for
near-term quantum computers to potentially demonstrate computational advantage
in solving combinatorial optimization problems. However, the viability of the
QAOA depends on how its performance and resource requirements scale with
problem size and complexity for realistic hardware implementations. Here, we
quantify scaling of the expected resource requirements by synthesizing
optimized circuits for hardware architectures with varying levels of
connectivity. Assuming noisy gate operations, we estimate the number of
measurements needed to sample the output of the idealized QAOA circuit with
high probability. We show the number of measurements, and hence total time to
solution, grows exponentially in problem size and problem graph degree as well
as depth of the QAOA ansatz, gate infidelities, and inverse hardware graph
degree. These problems may be alleviated by increasing hardware connectivity or
by recently proposed modifications to the QAOA that achieve higher performance
with fewer circuit layers.
Related papers
- Distributed Quantum Approximate Optimization Algorithm on Integrated High-Performance Computing and Quantum Computing Systems for Large-Scale Optimization [1.7099366779394252]
Quantum approximated optimization algorithm (QAOA) has shown promise for solving optimization problems by providing quantum speedup on gate-based quantum computing systems.
We propose a distributed QAOA (DQAOA), which leverages a high-performance computing-quantum computing integrated system.
We successfully optimize photonic structures using AL-DQAOA, indicating that solving real-world optimization problems using gate-based quantum computing is feasible with our strategies.
arXiv Detail & Related papers (2024-07-29T17:42:25Z) - Connecting the Hamiltonian structure to the QAOA performance and energy landscape [0.0]
Quantum Alternating Operator Ansatz (QAOA) is effective for solving Quadratic Unconstrained Binary Optimization problems.
This study emphasizes the algorithm's robustness and potential for optimization tasks on near-term quantum devices.
arXiv Detail & Related papers (2024-07-05T11:32:46Z) - Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
We propose a method for constructing quantum circuits which greatly reduces inter-device communication costs.
We show that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.
arXiv Detail & Related papers (2024-05-01T20:49:50Z) - Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems.
In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems.
We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
arXiv Detail & Related papers (2024-04-17T11:00:12Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
We provide a complete quantum circuit-level description of the algorithm from problem input to problem output.
We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
arXiv Detail & Related papers (2022-11-22T18:54:48Z) - 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) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Scaling of the quantum approximate optimization algorithm on
superconducting qubit based hardware [1.7150329136228708]
Quantum computers may provide good solutions to optimization problems by leveraging the Quantum Approximate Optimization Algorithm (QAOA)
QAOA is often presented as an algorithm for noisy hardware.
hardware constraints limit its applicability to problem instances that closely match the connectivity of the qubits.
This work highlights some obstacles to improve to make QAOA competitive such as gate fidelity, gate speed, and the large number of shots needed.
arXiv Detail & Related papers (2022-02-07T19:02:21Z) - 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) - Quantum Approximate Optimization of Non-Planar Graph Problems on a
Planar Superconducting Processor [29.928684308464796]
We demonstrate the application of the Google Sycamore superconducting qubit quantum processor to optimization problems with the quantum approximate optimization algorithm (QAOA)
For the first time, we observe, for the first time, that performance increases with circuit depth.
This behavior highlights the challenge of using near-term quantum computers to optimize problems on graphs differing from hardware connectivity.
arXiv Detail & Related papers (2020-04-08T18:44:34Z)
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.