Graph partitioning (GP) applikationer är allmänt förekommande i matematik, datavetenskap, kemi, fysik, biovetenskap, maskininlärning och komplexa system. Post Moores era supercomputing har gett oss en möjlighet att utforska nya metoder för traditionella grafalgoritmer om kvantdatorarkitekturer. I detta arbete utforskar vi grafpartitionering med hjälp av kvant annealing på D-Wave 2X-maskinen. Motiverad av en nyligen föreslagen grafbaserad elektronisk strukturteori tillämpad på kvantmolekylär dynamik (QMD) simuleringar, används grafpartitionering för att minska beräkningen av densitetsmatrisen till mindre delsystem vilket gör beräkningen mer beräkningseffektiv. Oöverskådlig graf partitionering som gemenskap kluster baserat på modularitet metrisk kan naturligt kartläggas in i Hamiltonian av kvantannealer. Å andra sidan, när begränsningar införs för uppdelning i lika delar och minimerar antalet skurna kanter mellan delar, krävs en quadratic okonstruerad binär optimering (QUBO) omformulering. Denna omformulering kan använda grafkomplementet för att passa problemet i Chimera grafen av kvantannealer. Delning i 2 delar och k delar samtidigt för godtycklig k demonstreras med riktvärden grafer, slumpmässiga grafer, och små material systemdensitetsmatris baserade grafer. Resultat för grafpartitionering med hjälp av kvant- och hybridklassic-quantum metoder visas vara jämförbara med nuvarande "state of the art" metoder och ibland bättre.
Ushijima-Mwesigwa demonstrerade grafen partitionering mekanism D-Wave datorer med hjälp av kvantangning verktyg på D-Wave 2X REF.
Graph Partitioning using Quantum Annealing on the D-Wave System
{'venue': "PMES'17", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}