Quantum IO-monaden är ett rent funktionellt gränssnitt mot kvantprogrammering som implementeras som ett Haskell-bibliotek. Samtidigt ger det en konstruktiv semantik av kvantprogrammering. QIO-monaden separerar reversibel (dvs. Enhetliga) och irreversibla (dvs. probabilistiska) beräkningar och ger en reversibel låt operation (ulet), så att vi kan använda ancillas (extra qubits) på ett modulärt sätt. QIO-program kan simuleras antingen genom att beräkna en sannolikhetsfördelning eller genom att inbädda den i IO monaden med hjälp av slumptalsgeneratorn. Som exempel presenterar vi ett fullständigt genomförande av Shors algoritm. Vi presenterar ett gränssnitt från ett rent funktionellt programmeringsspråk, Haskell, till kvantprogrammering: Quantum IO monad, och använder det för att implementera Shors faktoriseringsalgoritm. Genomförandet av QIO-monaden ger en konstruktiv semantik för kvantprogrammering, dvs. ett funktionellt program som också kan förstås som en matematisk modell av kvantdator. Faktum är att biblioteket Haskell QIO bara är en första approximation av en sådan semantik, vi skulle vilja flytta till ett mer uttrycksfullt språk som också är logiskt ljud. Här tänker vi på ett språk som Agda (Norell (2007)), som är baserat på Martin Löfs typteori. Vi har redan undersökt denna metod med funktionella specifikationer för effekter i ett klassiskt sammanhang (Swierstra och Altenkirch (2007, 2008); Swierstra (2008) ). På samma 1 2 Thorsten Altenkirch och Alexander S. Grön tid QIO monad ger en hög nivå gränssnitt till en hypotetisk kvantdator. För att göra presentationen tillgänglig för den icke-Haskell programmeraren ska vi ge en kort introduktion till språket i avsnitt 1.2. QIO-monaden separerar reversibel (dvs. Enhetliga) och irreversibla (dvs. probabilistiska) beräkningar och ger en reversibel låt operation (ulet), så att vi kan använda ancillas (extra qubits) på ett modulärt sätt. QIO-program kan simuleras antingen genom att beräkna en sannolikhetsfördelning eller genom att inbädda den i IO monaden med hjälp av slumptalsgeneratorn. En översikt över Quantum IO Monad (QIO) ges i avsnitt 1.3. Genom att utnyttja Haskells klasssystem kan vi presentera våra algoritmer på hög nivå och implementera abstraktioner med hjälp av funktionell programmeringsteknik. Vi beskriver genomförandet av Shors algoritm i någon detalj (avsnitt 1.5) också täcker den nödvändiga reversibla aritmetik (avsnitt 1.4). Den faktiska implementeringen av QIO behandlas i avsnitt 1.6, där vi fokuserar i detalj på utformningen av QIO kvantsimulatorfunktioner sim och kör. Quantum programmering kan utnyttja den märkliga naturen av kvantfysik för att uppnå klassiskt omöjliga, eller snarare ogenomförbara, uppgifter. Mest kända Shor algoritm visar att på en kvantdator kan vi faktor ett antal i polynom tid, därför kan vi bryta många krypteringssystem. Medan fysiker arbetar på att bygga fungerande kvantkretsar med mer än en handfull qubits, vi dataforskare brottas med de utmaningar quantum computing skapar för programvara: i att utforma algoritmer, som Shor s som utnyttjar kvantness; men också i att utforma språk som stöder abstraktioner relevanta för quantum computing. Se Gay (2006) och Rüdiger (2007) för de senaste språkundersökningarna. Här undersöker vi ett annat tillvägagångssätt: istället för att implementera ett nytt språk från grunden tillhandahåller vi ett monadiskt gränssnitt för att göra kvantprogrammering i Haskell - kvanten IO monad (QIO). Detta har ett antal fördelar: • vi kan utnyttja befintliga abstraktionsmedel som finns i Haskell för att strukturera våra kvantprogram, verkligen vi kommer att ge ett exempel på detta genom att genomföra klassen Qdata som relaterar klassiska data-typer med sina kvant motsvarigheter; • Vi kan utforska vilka semantiska primitiva är mest användbara för att strukturera kvantprogram, utan att binda sig till en viss syn alltför tidigt; Quantum IO Monad • vi kan utnyttja det befintliga stödet för Haskell, i form av verktyg och bibliotek för att utveckla våra kvantprogram. Vi anser att ett rent funktionellt tillvägagångssätt är idealiskt för detta projekt, eftersom det redan gör effekter explicita (i Haskell via IO monad) och är nära en matematisk semantik av kvantprogrammering (se våra inledande kommentarer om konstruktiv semantik). Medan QIO inser den infrastruktur vi behöver för att styra en kvantdator från Haskell, behöver vi inte vänta tills fysikerna utvecklar en praktisk kvantdator, vi kan använda samma gränssnitt för att köra en kvantsimulator. Vår strategi är inspirerad av den första författarens arbete med Wouter Swierstra om funktionella specifikationer för IO (Swierstra och Altenkirch (2007)). I själva verket ger vi något val här: vi kan inbädda QIO i IO monaden med pseudo-random siffror för att simulera kvant randomhet, vi kan statiskt beräkna sannolikhetsfördelningen av möjliga resultat med tanke på ett kvantprogram och vi kan simulera den klassiska delmängd av våra kvantoperationer direkt. Den senare är användbar för att testa komponenter effektivt eftersom kvantimuleringen genererar en betydande overhead. Alla de koder som beskrivs i detta kapitel, dvs. Genomförandet av QIO och de kvantalgoritmer som genomförs i den är tillgängliga från den andra författarens webbsida (Green (2008)). Det finns ett antal uppsatser om modellering av kvantprogrammering i Haskell, (Mu and Bird (2001); Sabry (2003); Karczmarczuk (2003); Vizzotto et al. (2006)........................................................................................................... De beskriver olika abstraktioner man kan använda för att simulera kvantberäkning i en funktionell miljö - dock är vårt tillvägagångssätt annorlunda genom att vi ger en hög nivå gränssnitt i andan av IO monad som ger ett gränssnitt till en hypotetisk kvantdator. Vårt tidigare arbete med QML (Altenkirch och Grattage (2005) ) föreslog en första ordning funktionell kvantprogrammering språk, det nuvarande arbetet är mer blygsam men ger oss en språngbräda för att experimentera med olika alternativa strukturer som är användbara för att strukturera kvantprogrammering och även för att genomföra framtida versioner av språk som QML.
Quantum IO Monad REF är inbäddat i Haskell och erbjuder konsekventa operationella semantik.
1 The Quantum IO Monad
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}