First-order transitions and the performance of quantum algorithms in random optimization problems

We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes expon...

Full description

Saved in:
Bibliographic Details
Published in:Physical review letters 2010-05, Vol.104 (20), p.207206-207206, Article 207206
Main Authors: Jörg, Thomas, Krzakala, Florent, Semerjian, Guilhem, Zamponi, Francesco
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c429t-29eb434562f84dae947f4d524f16e88385b002c52734011aeb618c5b8a55b5933
cites cdi_FETCH-LOGICAL-c429t-29eb434562f84dae947f4d524f16e88385b002c52734011aeb618c5b8a55b5933
container_end_page 207206
container_issue 20
container_start_page 207206
container_title Physical review letters
container_volume 104
creator Jörg, Thomas
Krzakala, Florent
Semerjian, Guilhem
Zamponi, Francesco
description We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the quantum adiabatic algorithm requires a time growing exponentially with system size to find the ground state of this problem.
doi_str_mv 10.1103/physrevlett.104.207206
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_755402688</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>755402688</sourcerecordid><originalsourceid>FETCH-LOGICAL-c429t-29eb434562f84dae947f4d524f16e88385b002c52734011aeb618c5b8a55b5933</originalsourceid><addsrcrecordid>eNo9kMtKxDAUhoMozjj6CpKdq44nadKmSxFvMKCIrkvanjqRpqlJKujTm2HU1YGf_8L5CDlnsGYM8stp-xU8fg4Y45qBWHMoORQHZMmgrLKSMXFIlgA5yyqAckFOQngHAMYLdUwWHFRRgqyWRN8aH2LmfIeeRq_HYKJxY6B67GjcIp3Q985bPbZIXU8_Zj3G2VI9vDlv4tYGakaacp2z1E3RWPOtdw108q4Z0IZTctTrIeDZ712R19ubl-v7bPN493B9tclawauY8QobkQtZ8F6JTmMlyl50koueFahUrmQDwFvJy1wAYxqbgqlWNkpL2cgqz1fkYt-bhj9mDLG2JrQ4DHpEN4e6lFJAel8lZ7F3tt6FRLGvJ2-s9l81g3pHt35KdJ_xc5PoJk3Ue7opeP47MTcWu__YH878ByUierg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>755402688</pqid></control><display><type>article</type><title>First-order transitions and the performance of quantum algorithms in random optimization problems</title><source>American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list)</source><creator>Jörg, Thomas ; Krzakala, Florent ; Semerjian, Guilhem ; Zamponi, Francesco</creator><creatorcontrib>Jörg, Thomas ; Krzakala, Florent ; Semerjian, Guilhem ; Zamponi, Francesco</creatorcontrib><description>We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the quantum adiabatic algorithm requires a time growing exponentially with system size to find the ground state of this problem.</description><identifier>ISSN: 0031-9007</identifier><identifier>EISSN: 1079-7114</identifier><identifier>DOI: 10.1103/physrevlett.104.207206</identifier><identifier>PMID: 20867059</identifier><language>eng</language><publisher>United States</publisher><ispartof>Physical review letters, 2010-05, Vol.104 (20), p.207206-207206, Article 207206</ispartof><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c429t-29eb434562f84dae947f4d524f16e88385b002c52734011aeb618c5b8a55b5933</citedby><cites>FETCH-LOGICAL-c429t-29eb434562f84dae947f4d524f16e88385b002c52734011aeb618c5b8a55b5933</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/20867059$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink></links><search><creatorcontrib>Jörg, Thomas</creatorcontrib><creatorcontrib>Krzakala, Florent</creatorcontrib><creatorcontrib>Semerjian, Guilhem</creatorcontrib><creatorcontrib>Zamponi, Francesco</creatorcontrib><title>First-order transitions and the performance of quantum algorithms in random optimization problems</title><title>Physical review letters</title><addtitle>Phys Rev Lett</addtitle><description>We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the quantum adiabatic algorithm requires a time growing exponentially with system size to find the ground state of this problem.</description><issn>0031-9007</issn><issn>1079-7114</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2010</creationdate><recordtype>article</recordtype><recordid>eNo9kMtKxDAUhoMozjj6CpKdq44nadKmSxFvMKCIrkvanjqRpqlJKujTm2HU1YGf_8L5CDlnsGYM8stp-xU8fg4Y45qBWHMoORQHZMmgrLKSMXFIlgA5yyqAckFOQngHAMYLdUwWHFRRgqyWRN8aH2LmfIeeRq_HYKJxY6B67GjcIp3Q985bPbZIXU8_Zj3G2VI9vDlv4tYGakaacp2z1E3RWPOtdw108q4Z0IZTctTrIeDZ712R19ubl-v7bPN493B9tclawauY8QobkQtZ8F6JTmMlyl50koueFahUrmQDwFvJy1wAYxqbgqlWNkpL2cgqz1fkYt-bhj9mDLG2JrQ4DHpEN4e6lFJAel8lZ7F3tt6FRLGvJ2-s9l81g3pHt35KdJ_xc5PoJk3Ue7opeP47MTcWu__YH878ByUierg</recordid><startdate>20100521</startdate><enddate>20100521</enddate><creator>Jörg, Thomas</creator><creator>Krzakala, Florent</creator><creator>Semerjian, Guilhem</creator><creator>Zamponi, Francesco</creator><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7X8</scope></search><sort><creationdate>20100521</creationdate><title>First-order transitions and the performance of quantum algorithms in random optimization problems</title><author>Jörg, Thomas ; Krzakala, Florent ; Semerjian, Guilhem ; Zamponi, Francesco</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c429t-29eb434562f84dae947f4d524f16e88385b002c52734011aeb618c5b8a55b5933</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2010</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Jörg, Thomas</creatorcontrib><creatorcontrib>Krzakala, Florent</creatorcontrib><creatorcontrib>Semerjian, Guilhem</creatorcontrib><creatorcontrib>Zamponi, Francesco</creatorcontrib><collection>PubMed</collection><collection>CrossRef</collection><collection>MEDLINE - Academic</collection><jtitle>Physical review letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Jörg, Thomas</au><au>Krzakala, Florent</au><au>Semerjian, Guilhem</au><au>Zamponi, Francesco</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>First-order transitions and the performance of quantum algorithms in random optimization problems</atitle><jtitle>Physical review letters</jtitle><addtitle>Phys Rev Lett</addtitle><date>2010-05-21</date><risdate>2010</risdate><volume>104</volume><issue>20</issue><spage>207206</spage><epage>207206</epage><pages>207206-207206</pages><artnum>207206</artnum><issn>0031-9007</issn><eissn>1079-7114</eissn><abstract>We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the quantum adiabatic algorithm requires a time growing exponentially with system size to find the ground state of this problem.</abstract><cop>United States</cop><pmid>20867059</pmid><doi>10.1103/physrevlett.104.207206</doi><tpages>1</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0031-9007
ispartof Physical review letters, 2010-05, Vol.104 (20), p.207206-207206, Article 207206
issn 0031-9007
1079-7114
language eng
recordid cdi_proquest_miscellaneous_755402688
source American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list)
title First-order transitions and the performance of quantum algorithms in random optimization problems
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-26T15%3A57%3A21IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=First-order%20transitions%20and%20the%20performance%20of%20quantum%20algorithms%20in%20random%20optimization%20problems&rft.jtitle=Physical%20review%20letters&rft.au=J%C3%B6rg,%20Thomas&rft.date=2010-05-21&rft.volume=104&rft.issue=20&rft.spage=207206&rft.epage=207206&rft.pages=207206-207206&rft.artnum=207206&rft.issn=0031-9007&rft.eissn=1079-7114&rft_id=info:doi/10.1103/physrevlett.104.207206&rft_dat=%3Cproquest_cross%3E755402688%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c429t-29eb434562f84dae947f4d524f16e88385b002c52734011aeb618c5b8a55b5933%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=755402688&rft_id=info:pmid/20867059&rfr_iscdi=true