Vi bevisar att det inte finns någon algoritm för att avgöra om en godtyckligt konstruerad Quantum Turing Machine har samma tidssteg för olika grenar av beräkningar. Vi kan därför inte undvika tanken på att stanna upp för att vara probabilistiska i Quantum Turing Machine. Vårt resultat tyder på att stoppa schema av Quantum Turing Machine och kvant komplexitet teori baserat på den befintliga stoppschema sholud ses över. PACS nummer: 03.67.Lx I [1] Myers påpekade att det finns ett problem i fall olika grenar av kvantberäkning på en Quantum Turing Machine (QTM) ta olika antal steg för att slutföra sin beräkning. Det vill säga, observation av att stoppa qubit kan förstöra beräkningen eftersom den väljer en gren av beräkning och kvantinterferensen förstörs efter valet. Därefter offentliggjordes flera dokument [2] [3] [4] om processen för att stoppa QTM. Under [2] föreslog Ozawa en möjlig lösning genom mätning av kvantnondemolition. Han visade att om man anser att en begränsad klass av QTMs sådan att stopp qubit och data slots inte ändras efter grenen faller i stopptillståndet, sannolikheten att få varje resultat vid en viss tid beror inte på det faktum att man använde stoppprotokollet eller inte. Det finns dock fortfarande ett problem. Även om man använder sig av det föreslagna protokollet är idén om att stoppa fortfarande probabilistisk. Det vill säga, en QTM med en ingång stannar ibland och stannar ibland inte. Om man inte kan bli av med möjligheten till ett sådant probabilistiskt stopp, kan man inte säga något säkert för ett experiment eftersom man inte kan säga om en händelse av stopp eller non-halting inträffade med sannolikhet en eller bara av misstag, säg med sannolikhet 10 −40. Bernstein och Vazirani [5] handlar endast om QTM vars grenar stannar samtidigt eller ingen av dem stannar. Om man begränsar QTM till en sådan klass, har man inte längre problemet. I detta brev kommer vi att visa att begränsningen inte är realistisk. Det vill säga, vi tar upp följande fråga: för en godtyckligt given QTM och en inmatning, kan vi avgöra om stoppet är probabilistiskt eller inte? Vi bevisar att svaret är negativt. Det innebär att det inte finns några nödvändiga och tillräckliga villkor för att förskriva icke-probabilistiska stopp av QTM. Vårt resultat tyder således på att det probabilistiska stoppet inte kan undvikas och verkar naturligt. En QTM [5] består av ett huvud, en processor och en oändlig tvåvägstejp med dataspår och andra (arbets)spår. Således den totala Hilbert utrymme spänns över av en komplett ortonormaliserad system { och x är en oändlig sekvens av alfabeten {B, 0, 1} (B kallas blank) med villkoret att antalet icke-blanka celler är ändlig och Z representerar huvudet position och q j  och q 0, q 1, · · ·, q N, q f } är ett internt tillstånd. Här q 0 betecknar ett initialtillstånd och q f ett stopptillstånd. En QTM är konstruerad genom att tilldela komplexa sannolikhetsamplituder (komponenter i en enhetlig matris) som uppfyller lokala regelvillkor. Det vill säga, endast övergångar mellan lokalt olika konfigurationer är tillåtna. Enligt [5], De komponenter antas vara beräkningsbara komplexa tal, eftersom annars kan vi inte konstruera QTM. I QTM skiljer sig stoppsystemet något från klassisk Turingmaskin på grund av minskningen av vågpaket [6]. För varje steg, Vi observerar om den interna staten är q f eller inte, med andra ord, Vi utför mätningen av operatören  påq f q f  på. När resultatet är 1, mäter vi dataplatserna i bandet och känner igen beräkningsresultatet. När resultatet är 0 observerar vi ingenting och fortsätter beräkningen. Alla de någonsin kända effektiva beräkningsshemen [7, 8] stannar med sannolikhet en i certatintid och stannar aldrig förr. För en godtyckligt konstruerad QTM kan dock de olika grenarna av beräkningen ha olika antal beräkningssteg i allmänhet. I ett sådant fall har den avstannande processen eller idén om att stoppa sig själv det problem som beskrivs ovan. Ett sätt att undvika en sådan svårighet är att endast överväga speciella typer av QTM:er och ingångar. Vi kallar ett par av en QTM Q och dess ingång x icke-probabilistiska stopp iff ett av följande villkor är uppfyllt. i) Det finns en t 0  till {1, 2, · · ·} sådan att i steg t 0, Q under x stannar med sannolikhet en och för s < t 0 det stannar med sannolikhet noll. ii) För alla steg stannar Q under x med sannolikhet noll. Ett par Q och x kallas probabilistiskt stopp när det inte är icke-probabilistiskt. Vi frågar om det finns en algoritm för att bedöma om en QTM och en inmatning är probabilistisk eller inte [9]. För att besvara ovanstående fråga, vi antar förekomsten av en sådan algoritm, (klassisk) Turing Machine (TM) T 0. Då kan vi visa motsägelse. TM T 0 fungerar så att du läser indata Q, x där Q är en QTM och x  till {0, 1} * är en indata och avgör om Q under indata x är probabilistisk stoppning eller inte. För reversibla TMs, T 1 och T 2, Låt oss definiera en speciell 1
• Miyadera och Ohya Ref diskuterar begreppet probabilistiskt stopp.
On Halting Process of Quantum Turing Machine
{'venue': 'Open Systems and Information Dynamics, Vol.12, No.3 261-264 (2005).', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Mathematics']}