Quantum algorithm of a set of quantum 2-sat problem

• URL: http://arxiv.org/abs/2009.02600v2
• Date: Sat, 31 Oct 2020 15:38:43 GMT
• Title: Quantum algorithm of a set of quantum 2-sat problem
• Authors: Yanglin Hu, Zhelun Zhang, Biao Wu
• Abstract summary: We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem, which is a generalization of 2-satisfiability (2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain. All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states. The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace. Our numerical results suggest that the time complexity of our algorithm is $O(n^{3.9})$ for yielding non-trivial solutions for problems with the number of clauses $m=dn(n-1)/2\ (d\lesssim 0.1)$. We discuss the advantages of our algorithm over the known quantum and classical algorithms.

Related papers

• A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
  We propose a quantum-classical hybrid algorithm with Ising model (HAWI) to address the Learning-With-Errors (LWE) problem. We identify the low-energy levels of the Hamiltonian to extract the solution, making it suitable for implementation on current noisy intermediate-scale quantum (NISQ) devices. Our algorithm is iterations, and its time complexity depends on the specific quantum algorithm employed to find the Hamiltonian's low-energy levels.
  arXiv  Detail & Related papers  (2024-08-15T05:11:35Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
  We show that max-k-SSAT is the computational algorithm on average when $m=Omega(n2+delta+epsilon)$ based on the average-case complexity theory. We also prove that max-k-SSAT is on average when $m=Omega(n2+delta+epsilon)$ based on the average-case complexity theory.
  arXiv  Detail & Related papers  (2024-03-05T15:03:47Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Quantum optimization algorithm based on multistep quantum computation [0.0]
  We present a quantum algorithm for finding the minimum of a function based on multistep quantum computation. In this algorithm, the dimension of the search space of the problem can be reduced exponentially step by step. We have tested the algorithm for some continuous test functions.
  arXiv  Detail & Related papers  (2023-06-30T01:58:23Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  This paper presents and describes a hybrid quantum computing strategy for solving 3-SAT problems. The performance of this approximation has been tested over a set of representative scenarios when dealing with 3-SAT from the quantum computing perspective.
  arXiv  Detail & Related papers  (2023-06-07T12:19:22Z)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks [0.0]
  We prove optimal lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup.
  arXiv  Detail & Related papers  (2021-06-03T17:22:08Z)

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.