Quantum cryptography, or quantum key distribution (QKD), provides a means of unconditionally secure communication. The security is in principle based on the fundamental laws of physics. Security proofs show that if quantum cryptography is appropriately implemented, even the most powerful eavesdropper cannot decrypt the message from a cipher. The implementations of quantum crypto-systems in real life may not fully comply with the assumptions made in the security proofs. Such discrepancy between the experiment and the theory can be fatal to the security of a QKD system. In this thesis we address a number of these discrepancies. A perfect single-photon source is often assumed in many security proofs. However, a weak coherent source is widely used in a real-life QKD implementation. Decoy state protocols have been proposed as a novel approach to dramatically improve the performance of a weak coherent source based QKD implementation without jeopardizing its security. Here, we present the first experimental demonstrations of decoy state protocols. Our experimental scheme was later adopted by most decoy state QKD implementations. In the security proof of decoy state protocols as well as many other QKD protocols, it is widely assumed that a sender generates a phase-randomized coherent state. This assumption has been enforced in few implementations. We close this gap in two steps: First, we implement and verify the phase randomization experimentally; second, we prove the security of a QKD implementation without the coherent state assumption. In many security proofs of QKD, it is assumed that all the detectors on the receiver's side have identical detection efficiencies. We show experimentally that this assumption may be violated in a commercial QKD implementation due to an eavesdropper's malicious manipulation. Moreover, we show that the eavesdropper can learn part of the final key shared by the legitimate users as a consequence of this violation of the assumptions.

Quantum cryptography, or quantum key distribution (QKD), provides a means of unconditionally secure communication. The security is in principle based on the fundamental laws of physics. Security proofs show that if quantum cryptography is appropriately implemented, even the most powerful eavesdropper cannot decrypt the message from a cipher. The implementations of quantum crypto-systems in real life may not fully comply with the assumptions made in the security proofs. Such discrepancy between the experiment and the theory can be fatal to the security of a QKD system. In this thesis we address a number of these discrepancies. A perfect single-photon source is often assumed in many security proofs. However, a weak coherent source is widely used in a real-life QKD implementation. Decoy state protocols have been proposed as a novel approach to dramatically improve the performance of a weak coherent source based QKD implementation without jeopardizing its security. Here, we present the first experimental demonstrations of decoy state protocols. Our experimental scheme was later adopted by most decoy state QKD implementations. In the security proof of decoy state protocols as well as many other QKD protocols, it is widely assumed that a sender generates a phase-randomized coherent state. This assumption has been enforced in few implementations. We close this gap in two steps: First, we implement and verify the phase randomization experimentally; second, we prove the security of a QKD implementation without the coherent state assumption. In many security proofs of QKD, it is assumed that all the detectors on the receiver's side have identical detection efficiencies. We show experimentally that this assumption may be violated in a commercial QKD implementation due to an eavesdropper's malicious manipulation. Moreover, we show that the eavesdropper can learn part of the final key shared by the legitimate users as a consequence of this violation of the assumptions.

In this thesis, I study bipartite discord between A and B in terms of the structure formed by the bipartite and tripartite entanglement found in the purified system ABC. I find that discord manifests itself only when there is both tripartite and bipartite entanglement present in the purification. This allows one to understand the asymmetry of quantum discord, D(A|B) ≠ D(B|A) in terms of entanglement monogamy. For the cases where AB has rank two and for two-mode Gaussian states, I find that discord also necessarily appears whenever there is tripartite and bipartite entanglement in ABC. As a result of this, some light is shed on a counter-intuitive property of Gaussian states: the presence of classical correlations necessarily requires the presence of quantum discord. Finally, these results are found to be closely linked to the protocol for remote activation of entanglement by a third party.

This thesis investigates three areas of the theory of graph homomorphisms: cores of graphs, the homomorphism order, and quantum homomorphisms. A core of a graph X is a vertex minimal subgraph to which X admits a homomorphism. Hahn and Tardif have shown that, for vertex transitive graphs, the size of the core must divide the size of the graph. This motivates the following question: when can the vertex set of a vertex transitive graph be partitioned into sets which each induce a copy of its core? We show that normal Cayley graphs and vertex transitive graphs with cores half their size always admit such partitions. We also show that the vertex sets of vertex transitive graphs with cores less than half their size do not, in general, have such partitions. Next we examine the restriction of the homomorphism order of graphs to line graphs. Our main focus is in comparing this restriction to the whole order. The primary tool we use in our investigation is that, as a consequence of Vizing's theorem, this partial order can be partitioned into intervals which can then be studied independently. We denote the line graph of X by L(X). We show that for all n ≥ 2, for any line graph Y strictly greater than the complete graph Kₙ, there exists a line graph X sitting strictly between Kₙ and Y. In contrast, we prove that there does not exist any connected line graph which sits strictly between L(Kₙ) and Kₙ, for n odd. We refer to this property as being ``n-maximal", and we show that any such line graph must be a core and the line graph of a regular graph of degree n. Finally, we introduce quantum homomorphisms as a generalization of, and framework for, quantum colorings. Using quantum homomorphisms, we are able to define several other quantum parameters in addition to the previously defined quantum chromatic number. We also define two other parameters, projective rank and projective packing number, which satisfy a reciprocal relationship similar to that of fractional chromatic number and independence number, and are closely related to quantum homomorphisms. Using the projective packing number, we show that there exists a quantum homomorphism from X to Y if and only if the quantum independence number of a certain product graph achieves |V(X)|. This parallels a well known classical result, and allows us to construct examples of graphs whose independence and quantum independence numbers differ. Most importantly, we show that if there exists a quantum homomorphism from a graph X to a graph Y, then ϑ̄(X) ≤ ϑ̄(Y), where ϑ̄ denotes the Lovász theta function of the complement. We prove similar monotonicity results for projective rank and the projective packing number of the complement, as well as for two variants of ϑ̄. These immediately imply that all of these parameters lie between the quantum clique and quantum chromatic numbers, in particular yielding a quantum analog of the well known ``sandwich theorem". We also briefly investigate the quantum homomorphism order of graphs.

This thesis investigates techniques for the automated optimization of quantum circuits. In the first part we develop an exponential time algorithm for synthesizing minimal depth quantum circuits. We combine this with effective heuristics for reducing the search space, and show how it can be extended to different optimization problems. We then use the algorithm to compute circuits over the Clifford group and T gate for many of the commonly used quantum gates, improving upon the former best known circuits in many cases. In the second part, we present a polynomial time algorithm for the re-synthesis of CNOT and T gate circuits while reducing the number of phase gates and parallelizing them. We then describe different methods for expanding this algorithm to optimize circuits over Clifford and T gates.

This dissertation addresses the issue of noise in quantum information processing devices. It is common knowledge that quantum states are particularly fragile to the effects of noise. In order to perform scalable quantum computation, it is necessary to suppress effective noise to levels which depend on the size of the computation. Various theoretical proposals have discussed how this can be achieved, under various assumptions about properties of the noise and the availability of qubits. We discuss new approaches to the suppression of noise, and propose experimental protocols characterizing the noise. In the first part of the dissertation, we discuss a number of applications of teleportation to fault-tolerant quantum computation. We demonstrate how measurement-based quantum computation can be made inherently fault-tolerant by exploiting its relationship to teleportation. We also demonstrate how continuous variable quantum systems can be used as ancillas for computation with qubits, and how information can be reliably teleported between these different systems. Building on these ideas, we discuss how the necessary resource states for teleportation can be prepared by allowing quantum particles to be scattered by qubits, and investigate the feasibility of an implementation using superconducting circuits. In the second part of the dissertation, we propose scalable experimental protocols for extracting information about the noise. We concentrate on information which has direct practical relevance to methods of noise suppression. In particular, we demonstrate how standard assumptions about properties of the noise can be tested in a scalable manner. The experimental protocols we propose rely on symmetrizing the noise by random application of unitary operations. Depending on the symmetry group use, different information about the noise can be extracted. We demonstrate, in particular, how to estimate the probability of a small number of qubits being corrupted, as well as how to test for a necessary condition for noise correlations. We conclude by demonstrating how, without relying on assumptions about the noise, the information obtained by symmetrization can also be used to construct protective encodings for quantum states.

This thesis describes a linear-optical device for performing generalized quantum measurements on quantum bits (qubits) encoded in photon polarization, the implementation of said device, and its use in two diff erent but related experiments. The device works by coupling the polarization degree of freedom of a single photon to a `mode' or `path' degree of freedom, and performing a projective measurement in this enlarged state space in order to implement a tunable four-outcome positive operator-valued measure (POVM) on the initial quantum bit. In both experiments, this POVM is performed on one photon from a two-photon entangled state created through spontaneous parametric down-conversion. In the fi rst experiment, this entangled state is viewed as a two-qubit photonic cluster state, and the POVM as a means of increasing the computational power of a given resource state in the cluster-state model of quantum computing. This model traditionally achieves deterministic outputs to quantum computations via successive projective measurements, along with classical feedforward to choose measurement bases, on qubits in a highly entangled resource called a cluster state; we show that `virtual qubits' can be appended to a given cluster by replacing some projective measurements with POVMs. Our experimental demonstration fully realizes an arbitrary three-qubit cluster computation by implementing the POVM, as well as fast active feed-forward, on our two-qubit photonic cluster state. Over 206 diff erent computations, the average output delity is 0.9832 +/- 0.0002; furthermore the error contribution from our POVM device and feedforward is only of order 10^-3, less than some recent thresholds for fault-tolerant cluster computing. In the second experiment, the POVM device is used to implement a deterministic protocol for remote state preparation (RSP) of arbitrary photon polarization qubits. RSP is the act of preparing a quantum state at a remote location without actually transmitting the state itself. We are able to remotely prepare 178 diff erent pure and mixed qubit states with an average delity of 0.995. Furthermore, we study the the fidelity achievable by RSP protocols permitting only classical communication, without shared entanglement, and compare the resulting benchmarks for average fidelity against our experimental results. Our experimentally-achieved average fi delities surpass the classical thresholds whenever classical communication alone does not trivially allow for perfect RSP.

This dissertation addresses the issue of noise in quantum information processing devices. It is common knowledge that quantum states are particularly fragile to the effects of noise. In order to perform scalable quantum computation, it is necessary to suppress effective noise to levels which depend on the size of the computation. Various theoretical proposals have discussed how this can be achieved, under various assumptions about properties of the noise and the availability of qubits. We discuss new approaches to the suppression of noise, and propose experimental protocols characterizing the noise. In the first part of the dissertation, we discuss a number of applications of teleportation to fault-tolerant quantum computation. We demonstrate how measurement-based quantum computation can be made inherently fault-tolerant by exploiting its relationship to teleportation. We also demonstrate how continuous variable quantum systems can be used as ancillas for computation with qubits, and how information can be reliably teleported between these different systems. Building on these ideas, we discuss how the necessary resource states for teleportation can be prepared by allowing quantum particles to be scattered by qubits, and investigate the feasibility of an implementation using superconducting circuits. In the second part of the dissertation, we propose scalable experimental protocols for extracting information about the noise. We concentrate on information which has direct practical relevance to methods of noise suppression. In particular, we demonstrate how standard assumptions about properties of the noise can be tested in a scalable manner. The experimental protocols we propose rely on symmetrizing the noise by random application of unitary operations. Depending on the symmetry group use, different information about the noise can be extracted. We demonstrate, in particular, how to estimate the probability of a small number of qubits being corrupted, as well as how to test for a necessary condition for noise correlations. We conclude by demonstrating how, without relying on assumptions about the noise, the information obtained by symmetrization can also be used to construct protective encodings for quantum states.

This thesis describes a linear-optical device for performing generalized quantum measurements on quantum bits (qubits) encoded in photon polarization, the implementation of said device, and its use in two diff erent but related experiments. The device works by coupling the polarization degree of freedom of a single photon to a `mode' or `path' degree of freedom, and performing a projective measurement in this enlarged state space in order to implement a tunable four-outcome positive operator-valued measure (POVM) on the initial quantum bit. In both experiments, this POVM is performed on one photon from a two-photon entangled state created through spontaneous parametric down-conversion. In the fi rst experiment, this entangled state is viewed as a two-qubit photonic cluster state, and the POVM as a means of increasing the computational power of a given resource state in the cluster-state model of quantum computing. This model traditionally achieves deterministic outputs to quantum computations via successive projective measurements, along with classical feedforward to choose measurement bases, on qubits in a highly entangled resource called a cluster state; we show that `virtual qubits' can be appended to a given cluster by replacing some projective measurements with POVMs. Our experimental demonstration fully realizes an arbitrary three-qubit cluster computation by implementing the POVM, as well as fast active feed-forward, on our two-qubit photonic cluster state. Over 206 diff erent computations, the average output delity is 0.9832 +/- 0.0002; furthermore the error contribution from our POVM device and feedforward is only of order 10^-3, less than some recent thresholds for fault-tolerant cluster computing. In the second experiment, the POVM device is used to implement a deterministic protocol for remote state preparation (RSP) of arbitrary photon polarization qubits. RSP is the act of preparing a quantum state at a remote location without actually transmitting the state itself. We are able to remotely prepare 178 diff erent pure and mixed qubit states with an average delity of 0.995. Furthermore, we study the the fidelity achievable by RSP protocols permitting only classical communication, without shared entanglement, and compare the resulting benchmarks for average fidelity against our experimental results. Our experimentally-achieved average fi delities surpass the classical thresholds whenever classical communication alone does not trivially allow for perfect RSP.

Quantum information processing devices promise to solve some problems more efficiently than their classical counterparts. The source of the speedup is the structure of quantum theory itself. In that sense, the physical units that are the building blocks of such devices are its power. The quest then is to find or manufacture a system that behaves according to quantum theory, and yet is controllable in such a way that the desired algorithms can be implemented. Candidate systems are benchmarked against general criteria to evaluate their success. In this thesis, I advance a particular system and present the progress made towards each of these criteria. The system is a three-qubit 13C solid-state nuclear magnetic resonance (NMR) based quantum processor. I report results concerning system characterization and control, pseudopure state preparation, and quantum error correction. I also report on using the system to test a central question in the foundation of quantum mechanics.