Bland modellerna för kvantberäkning, One-way Quantum Computer [10, 11] är en av de mest lovande förslagen för fysiskt förverkligande [12], och öppnar nya perspektiv för parallellisering genom att dra nytta av kvant trassling [2]. Eftersom en enkelriktad kvantberäkning baseras på kvantmätning, som i grunden är en icke-deterministisk evolution, har ett tillräckligt villkor för global determinism införts [4] som förekomsten av ett orsakssamband i en graf som ligger till grund för beräkningen. En O(n 3 )-algoritm har införts [6] för att hitta ett sådant orsakssamband när antalet utgångar och ingångsvertikalger i grafen är lika, annars var ingen polynomalgoritm 1 känd för att avgöra om en graf har ett orsakssamband eller inte. Vårt huvudsakliga bidrag är att införa en O(n 2 )-algoritm för att hitta ett orsakssamband, om något, oavsett antalet indata och utdata hörn är. Detta besvarar den öppna fråga som ställdes av Danos och Kashefi [4] och av de Beaudrap [6]. Dessutom visar vi att vår algoritm producerar ett optimalt flöde (flöde av minimalt djup). Förekomsten av ett orsakssamband är ett tillräckligt villkor för determinism, men det är inte ett nödvändigt villkor. En svagare version av orsakssambandet, kallat gflow (generaliserat flöde) har införts [3] och har visat sig vara ett nödvändigt och tillräckligt villkor för en familj av deterministiska beräkningar. Dessutom är kvantberäkningens djup övre avgränsat av g-flödets djup. Emellertid, förekomsten av en polynom tid algoritm som finner en gflow har angetts som en öppen fråga i [3]. I det här dokumentet svarar vi positivt på detta med en polynomalgoritm som ger ett optimalt g-flöde av en given graf och därmed finner en optimal korrigeringsstrategi till den icke-deterministiska evolutionen på grund av mätningar.
I REF har en polynomtidsalgoritm föreslagits som finner ett optimalt gflöde av en ingångsgeometri med n hörn som körs med O(n 4).
Finding Optimal Flows Efficiently
{'venue': 'Proc. of 35th ICALP (2008), 857-868', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}