Quantum algorithm of a set of quantum 2-sat problem

Autor:	Yanglin Hu, Zhelun Zhang, Biao Wu
Rok vydání:	2020
Předmět:	Set (abstract data type) Physics Quantum Physics Computer Science::Information Retrieval Quantum mechanics General Physics and Astronomy FOS: Physical sciences Quantum algorithm Adiabatic quantum computation Quantum Physics (quant-ph) Quantum
DOI:	10.48550/arxiv.2009.02600
Popis:	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 ≲ 0.1). We discuss the advantages of our algorithm over the known quantum and classical algorithms.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9486923bea606187fdd48235513f3fda Zobrazit plný text záznamu