Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem

• URL: http://arxiv.org/abs/2011.06218v1
• Date: Thu, 12 Nov 2020 05:54:57 GMT
• Title: Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Authors: Zhijie Tang and Eliot Kapit
• Abstract summary: We consider a range of unconventional modifications to Quantum Annealing (QA) In this problem, inspired by "transverse field chaos" in larger systems, classical and quantum methods are steered toward a false local minimum. We numerically study this problem by using a variety of new methods from the literature.
• Score: 2.2209333405427585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a range of unconventional modifications to Quantum Annealing (QA), applied to an artificial trial problem with continuously tunable difficulty. In this problem, inspired by "transverse field chaos" in larger systems, classical and quantum methods are steered toward a false local minimum. To go from this local minimum to the global minimum, all N spins must flip, making this problem exponentially difficult to solve. We numerically study this problem by using a variety of new methods from the literature: inhomogeneous driving, adding transverse couplers, and other types of coherent oscillations in the transverse field terms (collectively known as RFQA). We show that all of these methods improve the scaling of the time to solution (relative to the standard uniform sweep evolution) in at least some regimes. Comparison of these methods could help identify promising paths towards a demonstrable quantum speedup over classical algorithms in solving some realistic problems with near-term quantum annealing hardware.

Related papers

• Solving Sharp Bounded-error Quantum Polynomial Time Problem by Evolution methods [10.891099517614037]
  Counting ground state degeneracy of a $k$-local Hamiltonian is important in many fields of physics. Finding ground states of a $k$-local Hamiltonian is an easier problem of Quantum Merlin Arthur.
  arXiv  Detail & Related papers  (2024-06-05T13:00:22Z)
• Investigation into the Potential of Parallel Quantum Annealing for Simultaneous Optimization of Multiple Problems: A Comprehensive Study [0.0]
  Annealing is a technique to solve multiple optimization problems simultaneously. Annealing method minimizes idle qubits and holds promise for substantial speed-up.
  arXiv  Detail & Related papers  (2024-03-09T02:18:48Z)
• On the quantum time complexity of divide and conquer [42.7410400783548]
  We study the time complexity of quantum divide and conquer algorithms for classical problems. We apply these theorems to an array of problems involving strings, integers, and geometric objects.
  arXiv  Detail & Related papers  (2023-11-28T01:06:03Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Unraveling long-time quantum dynamics using flow equations [0.0]
  We present a new technique capable of simulating the non-equilibrium dynamics of two-dimensional quantum systems. We show that the method works well in both localized and delocalized phases. This approach shows that the exploration of intermediate-scale time evolution may be more feasible than is commonly assumed.
  arXiv  Detail & Related papers  (2023-08-24T18:10:16Z)
• Improving the speed of variational quantum algorithms for quantum error correction [7.608765913950182]
  We consider the problem of devising a suitable Quantum Error Correction (QEC) procedures for a generic quantum noise acting on a quantum circuit. In general, there is no analytic universal procedure to obtain the encoding and correction unitary gates. We address this problem using a cost function based on the Quantum Wasserstein distance of order 1.
  arXiv  Detail & Related papers  (2023-01-12T19:44:53Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Divide-and-conquer embedding for QUBO quantum annealing [0.0]
  We show that a problem-focused approach to embedding can improve performance by orders of magnitude. Our results show that a problem-focused approach to embedding can improve performance by orders of magnitude.
  arXiv  Detail & Related papers  (2022-11-03T23:22:06Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)

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.