As quantum computers edge closer to viability, it becomes necessary to create logic synthesis and minimization algorithms that take into account the particular aspects of quantum computers that differentiate them from classical computers. Since quantum computers can be functionally described as reversible computers with superposition and entanglement, both advances in reversible synthesis and increased utilization of superposition and entanglement in quantum algorithms will increase the power of quantum computing. One necessary component of any practical quantum computer is the computation of irreversible functions. However, very little work has been done on algorithms that synthesize and minimize irreversible functions into a reversible form. In this thesis, we present and implement a pair of algorithms that extend the best published solution to these problems by taking advantage of Product-Sum EXOR (PSE) gates, the reversible generalization of inhibition gates, which we have introduced in previous work [1,2]. We show that these gates, combined with our novel synthesis algorithms, result in much lower quantum costs over a wide variety of functions as compared to our competitors, especially on incompletely specified functions. Furthermore, this solution has applications for milti-valued and multi-output functions.

The exponential nature of Moore's law has inadvertently created huge data storage complexes that are scattered around the world. Data elements are continuously being searched, processed, erased, combined and transferred to other storage units without much regard to power consumption. The need for faster searches and power efficient data processing is becoming a fundamental requirement. Quantum computing may offer an elegant solution to speed and power through the utilization of the natural laws of quantum mechanics. Therefore, minimal cost quantum circuit implementation methodologies are greatly desired. This thesis explores the decomposition of group functions and the Walsh spectrum for implementing quantum canonical cascades with minimal cost. Three different methodologies, using group decomposition, are presented and generalized to take advantage of different quantum computing hardware, such as ion traps and quantum dots. Quantum square root of swap gates and fixed angle rotation gates comprise the first two methodologies. The third and final methodology provides further quantum cost reduction by more efficiently utilizing Hilbert spaces through variable angle rotation gates. The thesis then extends the methodology to realize a robust quantum circuit synthesis tool for single and multi-output quantum logic functions.

A great deal of theoretical activity has resulted from blending the fields of computer science and quantum mechanics. Out of this work has come the concept of a quantum computer, which promises to solve problems currently intractable for classical computers. This promise has, in turn, generated a large amount of effort directed toward investigating quantum computing experimentally. ¶ Quantum computing is difficult because fragile quantum superposition states of the computer’s register must be protected from the environment. This is made more difficult by the need to manipulate and measure these states. ¶ This thesis describes work that was carried out both to investigate and to demonstrate the utility of rare earth ion dopants for quantum computation. Dopants in solids are seen by many as a potential means of achieving scalable quantum computing. Rare earth ion dopants are an obvious choice for investigating such quantum computation. Long coherence times for both optical and nuclear spin transitions have been observed as well as optical manipulation of the spin states. The advantage that the scheme developed here has over nearly all of its competitors is that no complex nanofabrication is required. The advantages of avoiding nano-fabrication are two fold. Firstly, coherence times are likely to be adversely effected by the “damage” to the crystal structure that this manufacture represents. Secondly, the nano-fabrication presents a very serious difficulty in itself. ¶ Because of these advantages it was possible to perform two-qubit operations between independent qubits. This is the first time that such operations have been performed and presents a milestone in quantum computation using dopants in solids. It is only the second time two-qubit operations have been demonstrated in a solid. ¶ The experiments performed in this thesis were in two main areas: The first was the characterisation of hyperfine interactions in rare earth ion dopants; the second, simple demonstrations directly related to quantum computation. ¶ The first experiments that were carried out were to characterise the hyperfine interactions in Pr[superscript 3]+:Y[subscript 2]SiO[subscript 5]. The characterisation was the first carried out for the dopants in a site of such low symmetry. The resulting information about oscillator strengths and transition frequencies should prove indispensable when using such a system for quantum computation. It has already enabled an increase in the coherence times of nuclear spin transitions by two orders of magnitudes. ¶ The experiments directly related to the demonstration of quantum computation were all carried out using ensembles. The presence of a significant distribution of resonant frequencies, or inhomogeneous broadening, meant that many different sub-ensembles could be addressed, based on their resonant frequencies. Furthermore, the properties of the sub-ensembles could be engineered by optically pumping unwanted members to different hyperfine states away from resonance with the laser. ¶ A previously demonstrated technique for realising ensembles that could be used as single qubits was investigated and improved. Also, experiments were carried out to demonstrate the resulting ensembles’ utility as qubits. Further to this, ions from one of the ensembles were selected out, based on their interaction with the ions of another. Elementary two qubit operations were then demonstrated using these ensembles.

Recent advances in quantum computational science promise substantial improvements in the speed with which certain classes of problems can be computed. Various algorithms that utilize the distinctively non-classical characteristics of quantum mechanics have been formulated to take advantage of this promising new approach to computation. One such algorithm was formulated by David Deutsch and Richard Jozsa. By measuring the output of a quantum network that implements this algorithm, it is possible to determine with N 1 measurements certain global properties of a function f(x), where N is the number of network inputs. Classically, it may not be possible to determine these same properties without evaluating f(x) a number of times that rises exponentially as N increases. Hitherto, the potential power of this algorithm has been explored in the context of qubits, the quantum computational analogue of classical bits. However, just as one can conceive of classical computation in the context of non-binary logic, such as ternary or quaternary logic, so also can one conceive of corresponding higher-order quantum computational equivalents.<p>This thesis investigates the behaviour of the Deutsch-Jozsa algorithm in the context of these higher-order quantum computational forms of logic and explores potential applications for this algorithm. An important conclusion reached is that, not only can the Deutsch-Jozsa algorithms known computational advantages be formulated in more general terms, but also a new algorithmic property is revealed with potential practical applications.

This thesis deals with the question of what resources are necessary and sufficient for quantum computational speedup. In particular, we study what resources are required to promote fault tolerant stabilizer computation to universal quantum computation. In this context we discover a remarkable connection between the possibility of quantum computational speedup and negativity in the discrete Wigner function, which is a particular distinguished quasi-probability representation for quantum theory. This connection allows us to establish a number of important results related to magic state computation, an important model for fault tolerant quantum computation using stabilizer operations supplemented by the ability to prepare noisy non-stabilizer ancilla states. In particular, we resolve in the negative the open problem of whether every non-stabilizer resource suffices to promote computation with stabilizer operations to universal quantum computation. Moreover, by casting magic state computation as resource theory we are able to quantify how useful ancilla resource states are for quantum computation, which allows us to give bounds on the required resources. In this context we discover that the sum of the negative entries of the discrete Wigner representation of a state is a measure of its usefulness for quantum computation. This gives a precise, quantitative meaning to the negativity of a quasi-probability representation, thereby resolving the 80 year debate as to whether this quantity is a meaningful indicator of quantum behaviour. We believe that the techniques we develop here will be widely applicable in quantum theory, particularly in the context of resource theories.

Physical implementations of quantum computers will inevitably be subject to errors. However, provided that the error rate is below some threshold, it is theoretically possible to build fault tolerant quantum computers that are arbitrarily reliable. A particularly attractive fault tolerant proposal, due to its high threshold value, relies on Clifford group quantum computation and access to ancilla qubits. These ancilla qubits must be prepared in a particular state termed the 'magic' state. It is possible to distill faulty magic states into pure magic states, which is of significant interest for experimental work where perfect state preparation is generally not possible. This thesis describes a liquid state nuclear magnetic resonance based scheme for distilling magic states. Simulations are presented that indicate that such a distillation is feasible if a high level of experimental control is achieved. Preliminary experimental results are reported that outline the challenges that must be overcome to attain such precise control.

Given a bipartite density matrix ρ of a quantum state, the Quantum Separability problem (QUSEP) asks — is ρ entangled, or separable? In this thesis, we first strengthen Gurvits’ 2003 NP-hardness result for QUSEP by showing that the Weak Membership problem over the set of separable bipartite quantum states is strongly NP-hard, meaning it is NP-hard even when the error margin is as large as inverse polynomial in the dimension, i.e. is “moderately large”. Previously, this NP-hardness was known only to hold in the case of inverse exponential error. We observe the immediate implication of NP-hardness of the Weak Membership problem over the set of entanglement-breaking maps, as well as lower bounds on the maximum (Euclidean) distance possible between a bound entangled state and the separable set of quantum states (assuming P ≠ NP). We next investigate the entanglement-detecting capabilities of locally invariant unitary operations, as proposed by Fu in 2006. Denoting the subsystems of ρ as A and B, such that ρ_B = Tr_A(ρ), a locally invariant unitary operation U^B is one with the property U^B ρ_B (U^B)^† = ρ_B. We investigate the maximum shift (in Euclidean distance) inducible in ρ by applying I⊗U^B, over all locally invariant choices of U^B. We derive closed formulae for this quantity for three cases of interest: (pseudo)pure quantum states of arbitrary dimension, Werner states of arbitrary dimension, and two-qubit states. Surprisingly, similar to recent anomalies detected for non-locality measures, the first of these formulae demonstrates the existence of non-maximally entangled states attaining shifts as large as maximally entangled ones. Using the latter of these formulae, we demonstrate for certain classes of two-qubit states an equivalence between the Fu criterion and the CHSH inequality. Among other results, we investigate the ability of locally invariant unitary operations to detect bound entanglement.

In the study of quantum computation, data is represented in terms of linear operators which form a generalized model of probability, and computations are most commonly described as products of unitary transformations, which are the transformations which preserve the quality of the data in a precise sense. This naturally leads to unitary circuit models, which are models of computation in which unitary operators are expressed as a product of "elementary" unitary transformations. However, unitary transformations can also be effected as a composition of operations which are not all unitary themselves: the one-way measurement model is one such model of quantum computation. In this thesis, we examine the relationship between representations of unitary operators and decompositions of those operators in the one-way measurement model. In particular, we consider different circumstances under which a procedure in the one-way measurement model can be described as simulating a unitary circuit, by considering the combinatorial structures which are common to unitary circuits and two simple constructions of one-way based procedures. These structures lead to a characterization of the one-way measurement patterns which arise from these constructions, which can then be related to efficiently testable properties of graphs. We also consider how these characterizations provide automatic techniques for obtaining complete measurement-based decompositions, from unitary transformations which are specified by operator expressions bearing a formal resemblance to path integrals. These techniques are presented as a possible means to devise new algorithms in the one-way measurement model, independently of algorithms in the unitary circuit model.

This thesis is divided into two parts. In Part I we introduce a new formalism for quantum strategies, which specify the actions of one party in any multi-party interaction involving the exchange of multiple quantum messages among the parties. This formalism associates with each strategy a single positive semidefinite operator acting only upon the tensor product of the input and output message spaces for the strategy. We establish three fundamental properties of this new representation for quantum strategies and we list several applications, including a quantum version of von Neumann's celebrated 1928 Min-Max Theorem for zero-sum games and an efficient algorithm for computing the value of such a game. In Part II we establish several properties of a class of quantum operations that can be implemented locally with shared quantum entanglement or classical randomness. In particular, we establish the existence of a ball of local operations with shared randomness lying within the space spanned by the no-signaling operations and centred at the completely noisy channel. The existence of this ball is employed to prove that the weak membership problem for local operations with shared entanglement is strongly NP-hard. We also provide characterizations of local operations in terms of linear functionals that are positive and "completely" positive on a certain cone of Hermitian operators, under a natural notion of complete positivity appropriate to that cone. We end the thesis with a discussion of the properties of no-signaling quantum operations.

Physical implementations of quantum computers will inevitably be subject to errors. However, provided that the error rate is below some threshold, it is theoretically possible to build fault tolerant quantum computers that are arbitrarily reliable. A particularly attractive fault tolerant proposal, due to its high threshold value, relies on Clifford group quantum computation and access to ancilla qubits. These ancilla qubits must be prepared in a particular state termed the 'magic' state. It is possible to distill faulty magic states into pure magic states, which is of significant interest for experimental work where perfect state preparation is generally not possible. This thesis describes a liquid state nuclear magnetic resonance based scheme for distilling magic states. Simulations are presented that indicate that such a distillation is feasible if a high level of experimental control is achieved. Preliminary experimental results are reported that outline the challenges that must be overcome to attain such precise control.