I det här dokumentet överväger vi spinnsystem i tre rumsliga dimensioner, och bevisar att det lokala Hamiltonian problemet för 3D gitter med ansiktscentrerade kubikenheter celler, 4-lokalt översättningsinvarianta interaktioner mellan spin-3/2 partiklar och öppna gränsförhållanden är QMA EXP -fullständig. Vi går bortom en enkel inbäddning av tidigare hårda 1D-historik statskonstruktioner, och utnyttja en klassisk Wang tiling problem som binär räknare för att översätta en kub sida längd till en binär beskrivning för kontrollören indata. Vi använder oss vidare av en nyligen utvecklad beräkningsmodell som är särskilt väl lämpad för historiska tillståndskonstruktioner, och kombinerar den med en specifik kretskodning som visat sig vara universell för kvantberäkning. Dessa nya tekniker gör det möjligt för oss att avsevärt sänka den lokala spinndimensionen och överträffa det bästa översättningsinvarianta resultatet hittills med två storleksordningar (i antalet frihetsgrader per koppling). Detta gör våra modeller lika med den bästa non-translationally-invariant konstruktion. Hamiltonian operatörer används allmänt för att beskriva fysiska egenskaper hos multi-kropp kvantsystem, och är av största intresse för en rad discipliner som sträcker sig från teoretisk datavetenskap, till experimentell och kondenserad materia fysik. Medan dataforskare är intresserade av beräkningskraften hos olika modeller (t.ex. Hamiltonian kvantdatorer), för fysiker är det viktigt att beräkna strukturen av lågenergispektrum av kvantsystem. En av de mest grundläggande, men ändå grundläggande sådan fråga är att uppskatta marken tillstånd energi av en många-kropp spinn system med låga-intervall interaktioner, formellt känd som den lokala Hamilton problemet. Kitaevs seminala papper visar kvant-NP-hårdhet i det lokala Hamiltonska problemet för fallet att varje interaktion par som högst fem snurrar [1] motiverade betydande framsteg mot att förstå den beräknings komplexitet som uppstår i olika varianter av det lokala Hamiltonska problemet [2] [3] [4] [5] [6] [7] [8] [9] [10]. Dessa resultat är särskilt intressanta ur ett beräkningsperspektiv, som svarar på vilka familjer av Hamiltonians är "komplicerade nog" för att utföra universell kvantberäkning [11, 12]. Att analysera energinivåerna i de resulterande svåra instanserna krävde ofta utveckling av nya matematiska tekniker, som är av oberoende intresse t.ex. i samband med spektralanalys av stokastiska processer eller perturberingsteori. Men från perspektivet av experimentell fysik och materialvetenskap, de resulterande många kroppar kvantsystem är alltför konstruerade för att vara av relevans; antingen den lokala spinndimensionen är stor, koppling styrkor varierar från plats till plats, eller interaktionen grafer är inte geometriskt lokalt. Även om 1D-resultaten är intressanta och på sätt och vis de mest grundläggande modellerna att studera (eftersom varje 1D-hårdhetsresultat direkt innebär hårdhet i motsvarande högre-dimensionella konstruktioner), är de flesta kondenserade materiasystem i själva verket två- eller tredimensionella, och jämförelsen av lokal dimension mellan de bästa icke-translativt invarianta resultaten i 1D och 2D -8 [7], respektive 2 [3], visar att rör sig bortom 1D möjliggör en betydande minskning av latticespinns dimension. Det är därför en naturlig fråga att fråga sig om man kan gå längre än en enkel minskning från tidigare kända 1D-resultat, genom att utnyttja dessa extra dimensioner på ett icke-trivialt sätt (dvs. bortom en enkel inbäddning), men samtidigt behålla fina fysiska egenskaper såsom en vanlig lattice struktur och översättningssymmetrier. Vi kan till och med gå längre: finns det en familj av Hamiltonians på en fysiskt realistisk 3D kristall lattice med en QMA-hård mark tillstånd? Denna fråga är mycket relevant, eftersom sådana kristallstrukturer förekommer allmänt i naturen (t.ex. Ansiktscentrerade kubikgitter för natriumklorid, eller kroppscentrerade cesiumkloridkristaller). Den konstruktion som vi föreslår i detta dokument med högst 4 lokala interaktioner mellan snurr av dimension 4 ger 4 8 grader frihet, en ungefär två order-of-magnitude förbättring jämfört med en enkel inbäddning av den bästa endimensionella konstruktion, och i nivå med den bästa icke-translativt-invariant resultat. Det visar också att det bara finns omkring tre storleksordningar kvar mellan denna konstruktion och spinnsystem som vi möter varje dag (t.ex. Närmaste granne, snurr 1). I detta papper Familjen av spinnsystem vi studerar beskrivs av en Hamiltonian på en ansikte-centrerad kubik (cF) lattice som visas i fikon. 1................................................................ Mer exakt, vi börjar med en ändlig kubik lattice ι, där varje vertex och varje ansikte bär en 4-dimensionell spinn H loc = C 4; den totala Hilbert utrymme H är då tensor produkten av alla spins. För en geometriskt lokal Hamiltonian h agerar på k grannsnurr (på hörn, ansikten, eller båda), betecknar vi med h x den k-lokala operatören h när offset av en lattice vektor x  på, och agerar trivialt överallt annars; i fall att h x sticker ut ur ί, vi sätter h x  på 0. För en ändlig index uppsättning I, vi anser Hamiltonians av formen där varje h x i par som mest 4 snurrar, antingen inom en enda enhet cell, eller mellan angränsande enhetsceller. Genom konstruktion, är denna Hamiltonian translationally-invariant, och har öppna gränsförhållanden eftersom vi inte placera speciella interaktioner vid ansikten, kanter eller hörn av lattice cuboid. Indexet som jag inte beror på storleken på lattice, och inte heller någon av h i ; vi tillåter c i = c i ( och) att bero på systemets storlek. Detta gör att vi kan definiera en variant av den lokala Hamiltonian problem där input ges av en beskrivning av de lokala termerna för en Hamiltonian som i ekv. 1) (dvs. Matrisposter för de lokala termerna c i × h i, upp till polynomprecision), samt de tre sidolängderna W, H och D i lattice. Dessutom får vi två parametrar α < β som uppfyller β − α =  och ett löfte om att markens energi för H antingen är mindre än α, eller större än β. Det lokala Hamilton-problemet är då just frågan om att skilja mellan dessa två fall, och vi bevisar följande huvudteoret. QMA EXP liknar QMA, kvantanalogen av NP, men med en exponentiell tid kontrollör i stället för polynomialtime-en nödvändig teknikalitet för alla översättningsinvarianta resultat [8, 13], eftersom en n-qudit instans bara kan koda poly(log n) bitar av information (i detta fall sidan längder av lattice, som kodar indata i unary). I huvudsak kan ett QMA EXP - svårt problem verifieras i exponentiell tid på en kvantdator, precis som i fallet P vs NP förväntas det inte lösas lika effektivt (se bilaga A för detaljer). Vi ger ett rigoröst bevis på teorem 1 i bilaga G; i det följande vill vi ge en presentation på hög nivå av de idéer och bevistekniker som vi använder. Som tidigare hårdhet resultat, presenterar vi en explicit konstruktion av en familj av QMA EXP - hårda fall av denna variant av den lokala Hamiltoniska problemet. Vi kommer att använda oss av två typer av lokala termer, tiling och historia staten Hamiltonians, som båda har studerats i stor utsträckning, men mestadels oberoende av varandra. I vårt arbete kommer vi att använda varje metod till sin styrka: de klassiska tiling termer kommer att användas för att koda bootstrappning mekanism som ansvarar för den stora lokala dimensionen i tidigare arbete, medan historietillstånd termer kommer att användas som ett sätt att inbädda kvantberäkning delen. Först ska vi kort sammanfatta dessa metoder. Historia State Construction. Av definition, ett löfte problem Π är i QMA EXP om det finns en BQEXP kvantkrets-kallas "verifier"-så att för alla JA-instans l  och Π, det finns en poly-stor kvant tillstånd-kallas "vittne"-som kontrollören accepterar med sannolikhet ≥ 2/3; eller om l är en NO-intance, alla poly-sized vittnen avvisas med hög sannolikhet. Den exakta konstanten som används här är inte viktig, som för alla polynom p, man kan alltid förstärka en QMA EXP löfte problem sådan att distinktionen fungerar med sannolikhet ≥ 1 − 1/3 p (..) för ett exempel l  och Π med storlek (jfr. Anmärkning 1. Vi vet vidare att för alla QMA EXP löfte problem, kan vi alternativt få en så kallad kvantum ring maskin (QRM) som kontrollör (lemma 1). I korthet är en QRM en fast enhet R på (C d ) 2, som fungerar cykliskt på en ring av n dimension d qudits. Låna terminologi från Turing maskiner (TM)-som används för att bevisa universalitet av QRM modell-vi kallar enhet R huvudet av QRM, och qudit ringen är i huvudsak en TM tejp med cykliska gränsförhållanden. Bilda. 2 skildrar en sådan QRM och dess verksamhet i kretsnotering. Vi tar en specifik 2-qubit kvantport G och bevisar att den är universell, även när endast tillämpas på intilliggande qubits (lemma 4). Tillsammans med dess omvänt G † kan vi alltså använda Solovay-Kitaev för att approximera QRM-huvudet unitary R till inom precision. Eftersom vi kräver att QRM först skriver ut en instans l  ska Π på ringen, den resulterande kretsen C R har storlek  till C R  och = O (poly  och l) log 4 (1/ )), cf. Vad är det för fel på dig? För att matcha QRM-utvecklingen använder vi upprepade gånger C R på ett cykliskt sätt, som beskrivs i fikon. 2............................................................... I enlighet med traditionen kodar vi kretsen C R som en s.k. historiestat Hamiltonian. I sin enklaste form, en sådan Hamiltonian kodar övergångar för varje grind U i närvarande i C R = U T · · · U 1. Mer specifikt, på Hilbert utrymme.n och en grund {.j } j på C T +1, definierar vi var den första komponenten i Hilbert utrymme lagrar ett klockindex som tar reda på det aktuella steget i beräkningen. Man kan verifiera att ker(H prop ) spänns över av tillstånd av formen Vi säger att marktillståndet spänns av stater som kodar "historia" av beräkningen, vilket innebär att tillståndet för beräkningen efter t steg- och t -är insnärjd med "tid" registret  på (vi vill dock påpeka att detta är ett statiskt problem, och analogin med tid steg är rent pedagogiskt). En stor del av de overhead när det gäller lokal dimension eller interaktionsområde som finns i tidigare konstruktioner beror på att termerna i ekv. 2) inte nödvändigtvis är lokala. En vanlig metod för att konstruera en lokal klocka är att dela upp varje beräkningssteg i flera mellanliggande steg där ingen kvantport tillämpas, men där vissa interna omordningar sker som gör det möjligt för varje övergång att agera enbart på grannspinns. Detta gör det möjligt för varje grindoperation i ekv. (2) ska skrivas som en lokal interaktion. Problemet kvarstår dock att för varje lokal övergångsregel, för att veta vilken grind som ska tillämpas härnäst, måste man kunna identifiera det aktuella beräkningssteget lokalt och otvetydigt (för en omfattande diskussion se. [8, introd.]). Att veta när man ska tillämpa vilken övergångsregel som alltså kräver en potentiellt stor lokal Hilbert rymddimension, eller långdistansinteraktioner. Kvantringsmaskiner circumnavigerar en del av detta problem, eftersom endast en potentiellt mycket mindre krets C R måste tillämpas periodiskt. Men vi behöver fortfarande lokalt lagra det aktuella steget inom kretsen C R. I nästa avsnitt, förklarar vi hur vi använder diagonala Hamiltonska termer för att begränsa markutrymmet för vår Hamiltonian så att kretsbeskrivningen för C R exponeras i framkanten av kuboiden, på ett periodiskt upprepande sätt (jfr. Fikon. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Mer exakt, vi definierar en diagonal Hamiltonian H cl med spektral gap 1, och en degenererad markyta för vilken alla marken tillstånd av H cl + H prop kommer då att vara i en produktkonfiguration  och cl. Här är cl ett klassiskt produkttillstånd som tar en konfiguration som i fikon. 3 : i synnerhet en sträng som beskriver C R uttrycks, periodiskt, på framkanten. Lokala termer som i ekv. (2) kan sedan användas för att komma åt denna kretsbeskrivning utan någon uttrycklig kunskap om den aktuella positionen inom kretsen, som implicit ges av den plats på kuben där övergångsregeln tillämpas. Hamiltonian på en lattice, där varje term är en projektor på komplementet av tillåtna plattor på en specifik lattice plats (jfr. t.ex. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Som ett enkelt exempel, betrakta bara 2D-skikt B-typ sublattice från fikon. 1 Och anta att varje spinn är en qubit. Vi betecknar med vitt staten 0, och med röd skuggning staten 1. Anta att de enda plattor vi vill tillåta är de fyra som visas i fikon. 3 (utan roterade varianter). Genom att skriva en lokal term för varje kakel (där vi beställer motsvarande Hilbert utrymme (C 2 ) 4 som en tensor produkt av spinnet på baksidan, höger, front, och vänster, respektive), kan vi skriva en diagonal projektor  och 4 sådan att markytan spänns av kvanttillstånd som motsvarar giltiga kakel; som ett exempel, för den fjärde kakeln, vi skriver Vi kan således enkelt definiera en lokal Hamiltonian på lagret B-typ sublattice som i sin noll energi marken kodar giltiga tiling mönster, där intilliggande kanter matchar, om möjligt; om inte, marktillstånd energi Hamiltonian kommer att vara minst 1. Mer specifikt, om P indexerar alla rutor med fyra intilliggande spins, då kan vi skriva Hamiltonian som där h p i 1 agerar icke-trivialt endast på snurrar sitter på kanterna av kvadrat p. För de ovan nämnda plattorna, är det resulterande mönstret en binär räknare, som kan användas för att översätta djupet av en lattice, D, till en binär sträng representation av D i framkanten (jfr. Översta ansiktet i fikon. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Samma metod kan på motsvarande sätt användas för att genomdriva ett mer komplicerat tiling mönster i tre dimensioner, särskilt när man blandar strafftermer med olika vikter; för ett omfattande bevis på att motsvarande Hamiltonian markutrymme verkligen spänns av den bästa möjliga tiling vi hänvisar läsaren till [14, appdx.]. Hårda indicier för det lokala Hamiltonska problemet. Vi kommer nu att förklara hur dessa två tekniker-tilling och historia staten Hamiltonians-kan kombineras för att bevisa teorem 1. Som ett första steg definierar vi ett tiling mönster för att begränsa alla röda lager B snurr av kub-apart från toppen och sidolager, men inklusive det nedre lagret-till en specifik symbol som används ingen annanstans, och som vi betecknar med. Alla följande termer kan sedan konditioneras på dessa röda spins är antingen i tillstånd, eller inte; Detta gör att vi kan skilja mellan olika ansikten av kuboiden på ett översättningsförändrat sätt och med öppna gränsförhållanden. Denna teknik används vanligen i 1D (t.ex. [13] ), och vi utvidgar den till tre dimensioner. Som förklaras i den sista delen, definierar vi sedan fyra brickor som själv montera till en binär räknare; Detta gör att vi kan översätta djupet av kuben D till en sträng representation av D på den övre framkanten. Med hjälp av liknande brickor på sidorna av lattice, vi vind denna binära strängen ner och runt kuben i en moturs riktning; som det, strängen-som är den binära programbeskrivningen av QRM kretsen C R -uttrycks regelbundet på framkanten av lattice, som vi märka beräkningskanten, cf. Fikon. 3............................................................... Vi begränsar dessutom spinnen i det gröna lagret En sublattice i anslutning till denna beräkning kant för att vara i ett tillstånd som motsvarar på varandra följande par programbitar. Till exempel, om den binära programbeskrivningen är p 1, p 2, p 3, p 4, de gröna snurrar beror på (0, och (p 4, 0) respektive. En speciell kodning (jfr. Tabell 2) gör att vi kan översätta alla sådana binära par till en operation för att utföra på beräkning kanten. Alla begränsningar fram till denna punkt är diagonala i beräkningsgrunden och högst 4-lokala; vi samlar alla dessa statiska termer på cF lattice i Hamiltonian H stat. För att köra kretsen kodad av den binära strängen, kommer vi att anta att vi arbetar i marken utrymme H stat ; alla andra stater nödvändigtvis har energi ≥ 1. På den svarta lager A snurrar, vi partitionera Hilbert utrymme H Loc i C 2  och C 2; varje spinn antingen lagrar en qubit, eller det indikerar en av två "mover" symboler och. Vi skriver övergångsregler för de två pilarna, som flyttar dem runt kuben enligt deras riktning, medan de stannar på samma lager (jfr. Tillägg F.3.1. Varje qubit i deras väg trycks ner till nästa lager och cyklas en till höger om passeras av, Eller en till vänster om passerar av. När en pil anländer till beräkningskanten, en övergångsregel villkorad på programmet bitpar (p i, p i+1 ) (tillgängliga genom de gröna snurrar) utför 4 motsvarande beräkningssteg på de två intilliggande qubits. Pilen sätts sedan om till nästa lägre nivå, och hela proceduren upprepas. När pilen återvänder till beräkningskanten och är längst ner i skiktet, det finns ingen ytterligare framåt övergång; programmet avslutas. Symboliskt nog är de operationer vi kan utföra med denna grundläggande uppsättning instruktioner följande. Vi har ett kvanttillstånd av N qubits  på 1 Aq 2 · · · Aq N. I ett steg kan vi antingen. .... 1. cykla qubits medurs, till  medurs, till  skaq N  för 1 · · · N − 1, 2. cykla dem moturs, till  och 2 · · · ·  och N  till 1, 3. utföra en universell två-qubit kvantport G på de första två qubits, 4. eller utföra inversen av denna grind, d.v.s. G †................................................................. Vi bevisar i lemma 4 att det finns en sådan grind G som är universell för kvantberäkning, även om endast tillämpas på intilliggande qubits. Jämfört med tidigare samlar vi in alla historiska uttryck i Hamiltonian H hist. För oss, de lattice instanser av intresse är de där den binära strängen motsvarar en krets som approximerar chefen för en QMA EXP kontrollant QRM, dvs... C R (det faktum att de flesta program strängar inte representerar en sådan QRM är inte viktigt). I lemma 5 utför vi en noggrann analys av approximationsfelen, och visar att man verkligen kan välja höjd, bredd och djup på lattice (djup som motsvarar det kodade programmet, bredd till ringens storlek, och höjd till körtiden för kontrollören) så att historiken staten motsvarar en vittnesverifiering för alla fall l  och Π, där Π kan vara något lovande problem i QMA EXP. Vad som återstår att göra är att bestraffa ogiltiga historiktillståndskonfigurationer, såsom flera aktiva symboler, eller ingen aktiv symbol; samla dessa termer i en operatör P, som är den enda som kommer att använda sig av den skalningsfrihet som ges i ekv. (2)............................................................................................................... Slutligen säkerställer en inmatningspåföljd Π för beräkningen att vissa ancillas är korrekt initierade för beräkningen, och utmatningspåföljden Π ut höjer den lägsta energin för NO-instanser. Eftersom vår historia stat har grenar (eftersom inte alla övergångsregler vi skriver ner är helt entydiga), måste vi visa att H prop definierar en så kallad enhetlig märkt graf Laplacian och åberopa en nyligen beprövad variant av Kitaev geometriska lemma för detta fall, lemma 3. Med ett rigoröst bevis i bilaga G kan vi alltså visa att den övergripande 4-lokala översättningsinvariant Hamiltonian definieras på spin-3/2 cF lattice uppfyller löfte gapet λ min (H) ≤ − och (1/ poly  på engelska) om l är en JA-instans, och λ min (H) ≥ 0 annars. Detta avslutar konstruktionen, och påståendet av teorem 1 följer. Sökandet efter allt mer fysiskt realistiska familjer av QMA hårda lokala Hamiltonians har utan tvekan lett oss till allt mer påhittade konstruktioner. Den ökande komplexiteten som krävs när man går från icke-translativt-invarianta konstruktioner till translationell variabilitet är slående [13], och samma sak gäller för ansträngningarna att få den lokala dimensionen tillbaka inom rimligt intervall [8]. Å andra sidan måste nästan alltid någon grundläggande ny maskin utvecklas, för att öka vår kunskap om krets Hamiltonians: såsom att tillåta förgrening att hända i beräkningsbanan, eller med hjälp av enklare-att-implementera beräkningsmodeller (Quantum Ring Machines), av oberoende intresse t.ex. i samband med adiabatisk kvantberäkning ([15]). I vårt fall kombinerar vi vår konstruktion med Wang kakel, som enligt vår kunskap aldrig har använts för detta ändamål. Denna "outsourcing" av en del av beräkningen till ett klassiskt problem med begränsad tillfredsställelse sparar en betydande mängd overhead för kontrollmaskineriet som omger det faktiska kvantverifieringsförfarandet. Dessutom kan den enda universella kvantporten vara av oberoende intresse för andra tillämpningar, eftersom det är rimligt att föreställa sig en fysisk uppsättning där portar endast kan tillämpas på angränsande qubits i en krets. I själva verket visar vår 3D-konstruktion att den inbyggda beräkningen inte behöver vara mycket obskyr, och kan däremot även vara ganska elegant, vilket framgår av den mycket lägre erforderliga lokala dimensionen och därför mycket mindre antal möjliga interaktioner som krävs. Genom att gå bortom enkla rumsliga gitter kan vi visa att sådana strukturer stöder uppkomsten av mer komplexa beteenden, trots den inneboende symmetrin i de kristallgitter vi använder. Genom att utnyttja dessa nya funktioner kan vi minska den lokala dimensionen med två storleksordningar jämfört med det bästa hittills kända resultatet. Vi föreslår tre konkreta öppna problem.
Den lokala dimensionen har reducerats ännu mer till d = 4, för en översättningsinvariant Hamiltonian på en 3D lattice REF.
The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
{'venue': 'Journal of Mathematical Physics 58, 111901 (2017)', 'journal': None, 'mag_field_of_study': ['Physics', 'Computer Science']}