Research into quantum computation over the past 20 years has been very successful in stimulating the development of quantum cryptography (already in industrial application), the study of quantum information and the discovery of novel algorithms for traditionally hard and interesting problems such as prime factorisation. This paper attempts to explain why certain (strong and interesting) results in quantum computation still fall short of establishing universality (and programmability) for quantum computing. The notion of a computing device in a specific class is crucial for the development of a complexity theory and - more basically - establishes the notion of programmability. We review the well-established notions of universality in classical deterministic and probabilistic computing before moving on to examine the concept of a universal QTM introduced by Deutsch.
In hierdie bydrae word die vernaamste resultate oor sogenaamde universele kwantumberekening toegelig. Daar word 'n oorsig gegee oor die model wat gebaseer is op die kwantummeganiese Turing-masjien (KTM) van Deutsch. Ons lig die konsep van berekeningsuniversaliteit toe vir probabilistiese rekentoestelle en vergelyk dit met die vereistes wat aan 'n veronderstelde universele KTM gestel sou word. Die vermoede word geopper dat die semi-universele hibriede toestel (SUHT) wat deur die resultaat van Bernstein en Vazirani gesuggereer word, essensieel nie kwantummeganies is nie.
Research into quantum computation over the past 20 years has been very successful in stimulating the development of quantum cryptography (already in industrial application), the study of quantum information and the discovery of novel algorithms for traditionally hard and interesting problems such as prime factorisation. This paper attempts to explain why certain (strong and interesting) results in quantum computation still fall short of establishing universality (and programmability) for quantum computing. The notion of a computing device in a specific class is crucial for the development of a complexity theory and - more basically - establishes the notion of programmability. We review the well-established notions of universality in classical deterministic and probabilistic computing before moving on to examine the concept of a universal QTM introduced by Deutsch.
In hierdie bydrae word die vernaamste resultate oor sogenaamde universele kwantumberekening toegelig. Daar word 'n oorsig gegee oor die model wat gebaseer is op die kwantummeganiese Turing-masjien (KTM) van Deutsch. Ons lig die konsep van berekeningsuniversaliteit toe vir probabilistiese rekentoestelle en vergelyk dit met die vereistes wat aan 'n veronderstelde universele KTM gestel sou word. Die vermoede word geopper dat die semi-universele hibriede toestel (SUHT) wat deur die resultaat van Bernstein en Vazirani gesuggereer word, essensieel nie kwantummeganies is nie.
Daar is geen gebrek aan dekking in die laaste paar jaar in wetenskaplike joernale van die onderwerp van kwantumberekening nie. Tereg
ook, want dit is 'n nuwe idee met - tot sover- minstens een baie belangrike praktiese toepassing (ontbinding in priemfaktore) sodra die
tegnologie redelik omvattende berekenings kan hanteer. Die belangstelling in kwantumverwerking is aangevuur deur beide die besef
dat die toenemende miniaturisering noodwendig rekenaarwetenskaplikes met kwantumverskynsels sal konfronteer, en deur die begryp
van die potensiaal van massief parallelle verwerking deur die gebruik maak van die Hilbert-ruimtevoorstelling van kwantumstelsels en
die spesiale eienskappe van kwantumverstrengeling. Die onderwerp le by die sameloop van fisika, rekenaarwetenskap en wiskunde en
hierdie bydrae verken die idees van die drie gebiede wat die belangrikste rol in kwantumberekening speel en besin oor die definisies
van en die waarskynlike gebruik vir kwantumverwerking asook sy verhouding tot die klassieke berekeningskompleksiteit. Ten slotte
word 'n uitgebreide geannoteerde bibliografie verskaf as gids vir die geinteresseerde leser tot die literatuur in die onderwerp.
End
Quantum computing There has been no lack of coverage in the past few years in scientific journals of the topic of quantum computation. Rightly so, as
this is a novel idea with-so far-at least one very important practical application (prime factorisation) as soon as the technology can
accommodate reasonably sized computations. Interest in quantum computing has been sparked by both the realization that increasing
miniaturisation will eventually bring computer scientists face-to-face with quantum effects, and by the grasping of the potential for
massive parallelism inherent in the Hilbert space representation of quantum systems and in the special effects of quantum entanglement.
The topic lies at the confluence of physics, computer science and mathematics and this contribution reviews the ideas from these three
fields that play the most important role in quantum computation and reflects on the definitions of and prospective use for quantum
computing as well as its relation to classical computational complexity. Finally, an extended annotated bibliography is provided as a
guide for the interested reader to the literature in the subject.
End
Daar is geen gebrek aan dekking in die laaste paar jaar in wetenskaplike joernale van die onderwerp van kwantumberekening nie. Tereg ook, want dit is ’n nuwe idee met—tot sover—minstens ´ e´ en baie belangrike praktiese toepassing (ontbinding in priemfaktore) sodra die tegnologie redelik omvattende berekenings kan hanteer. Die belangstelling in kwantumverwerking is aangevuur deur beide die besef dat die toenemende miniaturisering noodwendig rekenaarwetenskaplikes met kwantumverskynsels sal konfronteer, en deur die begryp van die potensiaal van massief parallelle verwerking deur die gebruik maak van die Hilbert-ruimtevoorstelling van kwantumstelsels en die spesiale eienskappe van kwantumverstrengeling. Die onderwerp lˆ e by die sameloop van fisika, rekenaarwetenskap en wiskunde en hierdie bydrae verken die idees van di´ e drie gebiede wat die belangrikste rol in kwantumberekening speel en besin oor die definisies van en die waarskynlike gebruik vir kwantumverwerking asook sy verhouding tot die klassieke berekeningskompleksiteit. Ten slotte word ’n uitgebreide geannoteerde bibliografie verskaf as gids vir die ge¨ ınteresseerde leser tot die literatuur in di´ e onderwerp.AbstractQuantum computing There has been no lack of coverage in the past few years in scientific journals of the topic of quantum computation. Rightly so, as this is a novel idea with—so far—at least one very important practical application (prime factorisation) as soon as the technology can accommodate reasonably sized computations. Interest in quantum computing has been sparked by both the realization that increasing miniaturisation will eventually bring computer scientists face-to-face with quantum effects, and by the grasping of the potential for massive parallelism inherent in the Hilbert space representation of quantum systems and in the special effects of quantum entanglement. The topic lies at the confluence of physics, computer science and mathematics and this contribution reviews the ideas from these three fields that play the most important role in quantum computation and reflects on the definitions of and prospective use for quantum computing as well as its relation to classical computational complexity. Finally, an extended annotated bibliography is provided as a guide for the interested reader to the literature in the subject.
Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).
Deze PhD onderzoekt gespecialiseerde hardware om computationeel moeilijke problemen efficiënter op te lossen. Het werk richt zich op twee veelbelovende technologieën: fotonische kwantumcomputers en Ising-machines. Beide systemen verankeren computationele taken direct in hun dynamica, waardoor hun natuurlijke evolutie deze taken oplost. Deze vormen van rekenen bieden energiezuinige en schaalbare alternatieven voor traditionele digitale hardware. Het eerste deel draagt bij aan fotonische kwantumcomputing door efficiëntere klassieke algoritmen te ontwikkelen die realistische simulaties en optimalisaties mogelijk maken van lineaire optische circuits met fotonenteldetectoren. Dergelijke circuits worden gebruikt om niet-Gaussische kwantumtoestanden te genereren, zoals GKP-toestanden, die bijvoorbeeld dienen als bouwstenen voor universele kwantumcomputers. Verder introduceren we recurrente Gaussische kwantumnetwerken die tijdreeksen van kwantumtoestanden kunnen verwerken en beter presteren op diverse kwantummechanische communicatietaken. Het tweede deel onderzoekt analoge Ising-machines om combinatorische optimalisatieproblemen op te lossen. Dergelijke problemen zijn alomtegenwoordig in wetenschap en industrie. We identificeren een superieure methode om de verhoudingen tussen interne interacties en externe velden beter te beheersen, een prestatiebepalende balans die vaak ontbreekt in analoge Ising-machines. We breiden deze conclusies uit naar hogere-orde Ising-machines, die bijzonder geschikt zijn voor industrieel relevante ‘vervulbaarheidsproblemen’. Tot slot stellen we een efficiëntere manier voor om Max-3-Cut-problemen in Ising-machines te representeren, wat hun oplossingsprestaties verhoogt.
Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.