Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions

• URL: http://arxiv.org/abs/2302.09481v2
• Date: Sun, 2 Apr 2023 15:41:56 GMT
• Title: Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions
• Authors: Kosei Teramoto and Rudy Raymond and Eyuri Wakakuwa and Hiroshi Imai
• Abstract summary: Quantum Random Access Code (QRAC) to encode multiple variables of binary optimization in a single qubit. In this research, we extend the quantum-relaxation by using another QRAC which encodes three classical bits into two qubits. Also, we design a novel quantum relaxation that always guarantees a $2$x bit-to-qubit compression ratio.
• Score: 10.44923461503086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Random Access Optimizer (QRAO) is a quantum-relaxation based optimization algorithm proposed by Fuller et al. that utilizes Quantum Random Access Code (QRAC) to encode multiple variables of binary optimization in a single qubit. The approximation ratio bound of QRAO for the maximum cut problem is $0.555$ if the bit-to-qubit compression ratio is $3$x, while it is $0.625$ if the compression ratio is $2$x, thus demonstrating a trade-off between space efficiency and approximability. In this research, we extend the quantum-relaxation by using another QRAC which encodes three classical bits into two qubits (the bit-to-qubit compression ratio is $1.5$x) and obtain its approximation ratio for the maximum cut problem as $0.722$. Also, we design a novel quantum relaxation that always guarantees a $2$x bit-to-qubit compression ratio which is unlike the original quantum relaxation of Fuller~et~al. We analyze the condition when it has a non-trivial approximation ratio bound $\left(>\frac{1}{2}\right)$. We hope that our results lead to the analysis of the quantum approximability and practical efficiency of the quantum-relaxation based approaches.

Related papers

• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria. This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Alleviating the quantum Big-$M$ problem [0.237499051649312]
  Classically known as the "Big-$M$" problem, it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks.
  arXiv  Detail & Related papers  (2023-07-19T18:00:05Z)
• QAOA with $N\cdot p\geq 200$ [2.926192989090622]
  We demonstrate the execution of a hybrid quantum/classical optimization algorithm with high $Ncdot p$. This is the highest $Ncdot p$ demonstrated on hardware to date.
  arXiv  Detail & Related papers  (2023-03-03T16:32:49Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits [0.0]
  We embed 1-layer QAOA circuits into the larger class of parameterized Instantaneous Quantum Polynomial circuits. The use of analytic expressions to find optimal parameters makes our protocol robust against barren plateaus and hardware noise. Our protocol outperforms 1-layer QAOA on the recently released Quantinuum H2 trapped-ion quantum hardware and emulator.
  arXiv  Detail & Related papers  (2022-10-11T15:16:44Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers. We find that classical solvers are capable of producing high-quality approximate solutions in linear time complexity. Other problems, such as different graphs, weighted MaxCut, maximum independent set, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
  arXiv  Detail & Related papers  (2022-06-07T20:59:19Z)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  We devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tildeO(N-2/3)$ with privacy guarantees.
  arXiv  Detail & Related papers  (2020-07-23T10:50:42Z)

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.