English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

One of the most important questions in studying quantum computation is:whether a quantum computer can solve NP-complete problems more efficiently thana classical computer? In 2000, Farhi, et al. (Science, 292(5516):472--476,2001) proposed the adiabatic quantum optimization (AQO), a paradigm thatdirectly attacks NP-hard optimization problems. How powerful is AQO? Early on,van Dam and Vazirani claimed that AQO failed (i.e. would take exponential time)for a family of 3SAT instances they constructed. More recently, Altshuler, etal. (Proc Natl Acad Sci USA, 107(28): 12446--12450, 2010) claimed that AQOfailed also for random instances of the NP-complete Exact Cover problem. Inthis paper, we make clear that all these negative results are only for aspecific AQO algorithm. We do so by demonstrating different AQO algorithms forthe same problem for which their arguments no longer hold. Whether AQO fails orsucceeds for solving the NP-complete problems (either the worst case or theaverage case) requires further investigation. Our AQO algorithms for ExactCover and 3SAT are based on the polynomial reductions to the NP-completeMaximum-weight Independent Set (MIS) problem.

Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems