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.

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.

The fullerene cage provides an ideal, isolated environment for trapping spin active atoms such as nitrogen or phosphorous. Alignment of these endohedral fullerenes in linear arrays would have applications in quantum computing as the interactions between spin-active molecules can be easily controlled. Self-assembled molecular networks such as block copolymers, Langmuir-Blodgett films, and self-assembled monolayers are ideal for this purpose as the spacing and geometry can be easily tuned. This dissertation will discuss using each of these methods to achieve alignment or orientation of fullerenes for application in quantum information processing.

Programmable reversible logic is emerging as a prospective logic design style for implementation in modern nanotechnology and quantum computing with minimal impact on circuit heat generation. Recent advances in reversible logic using and quantum computer algorithms allow for improved computer architecture and arithmetic logic unit designs. In this paper, a 2*2 Swap gate which is a reduced implementation in terms of quantum cost and delay to the previous Swap gate is presented. Next, a novel 3*3 programmable UPG gate capable of calculating the fundamental logic calculations is presented and verified, and its advantages over the Toffoli and Peres gates are discussed. The UPG is then implemented in a reduced design for calculating n-bit AND, n-bit OR and n-bit ZERO calculations. Then, two 3*3 RMUX gates capable of multiplexing two input values with reduced quantum cost and delay compared to the previously existing Fredkin gate is presented and verified. Next, 4*4 reversible gate is presented and verified which is capable of producing the calculations necessary for two-bit comparisons. The UPG and RC are implemented in the design of novel sequential and tree-based comparators. Then, two novel 4*4 reversible logic gates (MRG and PAOG) are proposed with minimal delay, and may be configured to produce a variety of logical calculations on fixed output lines based on programmable select input lines. A 5*5 structure (MG) is proposed that extends the capabilities of both the MRG and PAOG. The comparator designs are verified and its advantages to previous designs are discussed. Then, reversible implementations of ripple-carry, carry-select and Kogge-Stone carry look-ahead adders are analyzed and compared. Next, implementations of the Kogge-Stone adder with sparsity-4, 8 and 16 were designed, verified and compared. The enhanced sparsity-4 Kogge-Stone adder with ripple-carry adders was selected as the best design, and its implemented in the design of a 32-bit arithmetic logic unit is demonstrated. The proposed ALU design is verified and its advantages over the only existing ALU design are quantitatively analyzed.

Andrea Damascelli is looking to usher in a new era of quantum computing with a groundbreaking technique that defies all nanotechnology research to date.

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.

<p>Trapped ion systems are the leading candidate for quantum information processing because many of the critical components have already been demonstrated. Scaling trapped ion systems to large numbers of ions is currently believed possible, but much work remains to prove it. Microfabricated surface ion traps are increasing in popularity for their ease of mass production and their ability to manipulate individual ions and interact arbitrary pairs of ions. Even with the advent of scalable ion traps, detection of an individual ion trapped in a high vacuum poses a challenge. The internal state of the ion chosen for a quantum bit can be measured via exposure to a probe beam that causes one state to scatter light (a "bright" state), but not the other state (a "dark" state). In free space, a single ion acts like a point source that emits in all directions; a standard two inch lens system can only collect about 2% of the light emitted by the ion. Poor light collection results in a high error rate and slow determination of the internal state of the ion. Fast, high fidelity state detection is necessary for quantum error correction and loophole-free Bell experiments at short (less than 100\,km) distances, and high efficiency collection is necessary to rapidly interconnect separate quantum computers. We demonstrate state detection fidelities of 99%, 99.856(8)% and 99.915(7) % which correspond to detection times of 10.5, 28.1 and 99.8 us, respectively.</p> / Dissertation

Superdense coding and quantum teleportation are two phenomena which were not possible without prior entanglement. In superdense coding, one sends n bits of information using n/2 qubits in the presence of shared entanglement. However, we show that n bits of information cannot be sent with less than n bits of communication in LOCC protocols even in the presence of prior entanglement. This is an interesting result which will be used in the rest of this thesis. Quantum teleportation uses prior entanglement and classical communication to send an unknown quantum state. Remote state preparation (RSP) is the same distributed task, but in the case that the sender knows the description of the state to be sent, completely. We study the communication complexity of approximate remote state preparation in which the goal is to prepare an approximation of the desired quantum state. Jain showed that the worst-case error communication complexity of RSP can be bounded from above in terms of the maximum possible information in an encoding [18]. He also showed that this quantity is a lower bound for communication complexity of exact remote state preparation [18]. In this thesis, we characterize the worst-case error and average-case error communication complexity of remote state preparation in terms of non-asymptotic information-theoretic quantities. We also utilize the bound we derived for the communication complexity of LOCC protocols in the first part of the thesis, to show that the average-case error communication complexity of RSP can be much smaller than the worst-case.