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
- 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) - 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) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [7.962205145083434]
We propose the first online quantum algorithm for zero-sum games with $tilde O(1)$ regret under the game setting.
Our quantum algorithm computes an $varepsilon$-approximate Nash equilibrium of an $m times n$ matrix zero-sum game in quantum time.
arXiv Detail & Related papers (2023-04-27T14:02:54Z) - 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) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Reflection-Based Adiabatic State Preparation [0.0]
Our algorithm deploys a sequence of reflections determined from eigenspaces of instantaneous Hamiltonians defined along an adiabatic schedule.
We provide numerical evidence suggesting that, for search problems, our algorithm can find a solution faster, on average, than Grover's search.
arXiv Detail & Related papers (2021-11-10T00:03:00Z) - 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.