Graph states are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing. Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC + LPM + CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. This question is of interest for effective routing or state preparation decisions in a quantum network or distributed quantum processor and also in the design of quantum repeater schemes and quantum error-correction codes. We first show that deciding whether a graph state |G) can be transformed into another graph state |G) using LC + LPM + CC is NP-complete, which was previously not known. We also show that the problem remains NP-complete even if |G) is restricted to be the GHZ-state. However, we also provide efficient algorithms for two situations of practical interest. Our results make use of the insight that deciding whether a graph state |G) can be transformed to another graph state |G) is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G' is a vertex-minor of a graph G. The computational complexity of the vertex-minor problem was prior to this paper an open question in graph theory. We prove that the vertex-minor problem is NP-complete by relating it to a new decision problem on 4-regular graphs which we call the semi-ordered Eulerian tour problem.@en

Quantum computers promise to be a revolutionary new technology. However, in order to realise this promise many hurdles must first be overcome. In this thesis we investigate two such hurdles: the presence of noise in quantum computers and limitations on the connectivity and control in large scale quantum computing architectures.In order to combat noise in quantum devices we must first characterize this noise. To do this several diagnostic tools have been developed over the last two decades. The current industry standard for such a diagnostic tool is called randomized benchmarking. Randomized benchmarking doesn't give a full characterization of the noise afflicting the quantum device but rather attempts to give some indication of of the device's average behavior, captured in a quantity called the average fidelity. Because it does not endeavor to characterize every small detail of the noise it can be efficiently applied even to very large quantum devices. However, with this power also comes increased complexity. Randomized benchmarking has a lot of moving parts, and some fairly strong assumptions must be made in order to guarantee its correctness. In this thesis we attempt to justify these assumptions and if possible remove or weaken them, making randomized benchmarking a more robust and general tool. In chapter 6 of this thesis we investigate the finite statistics of randomized benchmarking. We prove strong bounds on the number of samples needed to perform rigorous randomized benchmarking. To do this we make use tools from representation theory. In particular we use a characterization of certain representations of the Clifford group, which we develop in chapter 5. In chapter 7 we re-use these tools to also bound the number of samples needed to perform rigorous unitarity randomized benchmarking, a newer variant of randomized benchmarking quickly gaining in popularity. These results retroactively justify the use of randomized benchmarking in an experimental setting and also provide guidance on optimal statistical practices in the context of randomized benchmarking. In chapter 8 we expand upon the standard randomized benchmarking protocol and formulate a new class of protocols which we call character randomized benchmarking. This new class of protocols removes a critical assumption made in standard randomized benchmarking, making character randomized benchmarking vastly more generally applicable. To show the advantages of character randomized benchmarking we implement it in an experiment characterizing the noise in a Si/SiGe quantum dot device. This experiment is detailed in chapter 9. Finally we deal with the second main topic of this thesis in chapter 10. Large scale quantum computer will, like classical computers, face limitations in the connectivity between different parts of the computer. This is due to a fundamental law in computer design called Rent's rule, which states that the number of wires connecting a (quantum) computer chip to the outside world is much smaller than the number of components in that chip. This means the individual components of the chip can not be controlled individually in parallel. Given that parallelism is absolutely critical for the functioning of quantum computers this is a serious problem for the development of large scale quantum computers. Luckily it is possible to organize quantum computing devices in such a way that they can be controlled using a relatively small amount of input wires. One example of such an organization is called a crossbar architecture. Recently a proposal was made for a crossbar architecture quantum computer in quantum dots, and in chapter 10 of this thesis we investigate in detail the advantages and disadvantages of such an architecture. We focus in particular on its effect on standard quantum error correction procedures, a key part of a functioning quantum computer, and one where parallel control of all parts of the quantum device is essential. @en

A graph H is a vertex-minor of a graph G if it can be reached from G by the successive application of local complementations and vertex deletions. Vertex-minors have been the subject of intense study in graph theory over the last decades and have found applications in other fields such as quantum information theory. Therefore it is natural to consider the computational complexity of deciding whether a given graph G has a vertex-minor isomorphic to another graph H. Here we prove that this decision problem is NP-complete, even when restricting H and G to be circle graphs, a class of graphs that has a natural relation to vertex-minors.@en

A central challenge for the scaling of quantum computing systems is the need to control all qubits in the system without a large overhead. A solution for this problem in classical computing comes in the form of so-called crossbar architectures. Recently we made a proposal for a large-scale quantum processor (Li et al arXiv:1711.03807 (2017)) to be implemented in silicon quantum dots. This system features a crossbar control architecture which limits parallel single-qubit control, but allows the scheme to overcome control scaling issues that form a major hurdle to large-scale quantum computing systems. In this work, we develop a language that makes it possible to easily map quantum circuits to crossbar systems, taking into account their architecture and control limitations. Using this language we show how to map well known quantum error correction codes such as the planar surface and color codes in this limited control setting with only a small overhead in time. We analyze the logical error behavior of this surface code mapping for estimated experimental parameters of the crossbar system and conclude that logical error suppression to a level useful for real quantum computation is feasible.@en

We propose network benchmarking: a procedure to efficiently benchmark the quality of a quantum network link connecting quantum processors in a quantum network. This procedure is based on the standard randomized benchmarking protocol and provides an estimate for the fidelity of a quantum network link. We provide statistical analysis of the protocol as well as a simulated implementation inspired by nitrogen-vacancy center systems using Netsquid, a special purpose simulator for noisy quantum networks.@en

We report the first complete characterization of single-qubit and two-qubit gate fidelities in silicon-based spin qubits, including cross talk and error correlations between the two qubits. To do so, we use a combination of standard randomized benchmarking and a recently introduced method called character randomized benchmarking, which allows for more reliable estimates of the two-qubit fidelity in this system, here giving a 92% fidelity estimate for the controlled-Z gate. Interestingly, with character randomized benchmarking, the two-qubit gate fidelity can be obtained by studying the additional decay induced by interleaving the two-qubit gate in a reference sequence of single-qubit gates only. This work sets the stage for further improvements in all the relevant gate fidelities in silicon spin qubits beyond the error threshold for fault-tolerant quantum computation.@en

Graph states, which include Bell states, Greenberger-Horne-Zeilinger (GHZ) states, and cluster states, form a well-known class of quantum states with applications ranging from quantum networks to error-correction. Whether two graph states are equivalent up to single-qubit Clifford operations is known to be decidable in polynomial time and has been studied in the context of producing certain required states in a quantum network in relation to stabilizer codes. The reason for the latter is that single-qubit Clifford equivalent graph states exactly correspond to equivalent stabilizer codes. We here consider that the computational complexity of, given a graph state |G«, counting the number of graph states, single-qubit Clifford equivalent to |G«. We show that this problem is #P-complete. To prove our main result, we make use of the notion of isotropic systems in graph theory. We review the definition of isotropic systems and point out their strong relation to graph states. We believe that these isotropic systems can be useful beyond the results presented in this paper.@en

Critical to the construction of large scale quantum networks, i.e. a quantum internet, is the development of fast algorithms for managing entanglement present in the network. One fundamental building block for a quantum internet is the distribution of Bell pairs between distant nodes in the network. Here we focus on the problem of transforming multipartite entangled states into the tensor product of bipartite Bell pairs between specific nodes using only a certain class of local operations and classical communication. In particular we study the problem of deciding whether a given graph state, and in general a stabilizer state, can be transformed into a set of Bell pairs on specific vertices using only single-qubit Clifford operations, single-qubit Pauli measurements and classical communication. We prove that this problem is NP-Complete.@en

The q-qubit Clifford group, that is, the normalizer of the q-qubit Pauli group in U(2q), is a fundamental structure in quantum information with a wide variety of applications. We characterize all irreducible subrepresentations of the two-copy representation φ⊗2 of the Clifford group on the two-fold tensor product of the space of linear operators M2q⊗2. In the companion paper [Helsen et al., e-print arXiv:1701.04299 (2017)], we apply this result to improve the statistics of randomized benchmarking, a method for characterizing quantum systems.@en

Unitarity randomized benchmarking (URB) is an experimental procedure for estimating the coherence of implemented quantum gates independently of state preparation and measurement errors. These estimates of the coherence are measured by the unitarity. A central problem in this experiment is relating the number of data points to rigorous confidence intervals. In this work we provide a bound on the required number of data points for Clifford URB as a function of confidence and experimental parameters. This bound has favorable scaling in the regime of near-unitary noise and is asymptotically independent of the length of the gate sequences used. We also show that, in contrast to standard randomized benchmarking, a nontrivial number of data points is always required to overcome the randomness introduced by state preparation and measurement errors even in the limit of perfect gates. Our bound is sufficiently sharp to benchmark small-dimensional systems in realistic parameter regimes using a modest number of data points. For example, we show that the unitarity of single-qubit Clifford gates can be rigorously estimated using few hundred data points under the assumption of gate-independent noise. This is a reduction of orders of magnitude compared to previously known bounds.@en

We introduce spectral quantum tomography, a simple method to extract the eigenvalues of a noisy few-qubit gate, represented by a trace-preserving superoperator, in a SPAM-resistant fashion, using low resources in terms of gate sequence length. The eigenvalues provide detailed gate information, supplementary to known gate-quality measures such as the gate fidelity, and can be used as a gate diagnostic tool. We apply our method to one- and two-qubit gates on two different superconducting systems available in the cloud, namely the QuTech Quantum Infinity and the IBM Quantum Experience. We discuss how cross-talk, leakage and non-Markovian errors affect the eigenvalue data.@en

Randomized benchmarking is a technique for estimating the average fidelity of a set of quantum gates. However, if this gateset is not the multi-qubit Clifford group, robustly extracting the average fidelity is difficult. Here, we propose a new method based on representation theory that has little experimental overhead and robustly extracts the average fidelity for a broad class of gatesets. We apply our method to a multi-qubit gateset that includes the T-gate, and propose a new interleaved benchmarking protocol that extracts the average fidelity of a two-qubit Clifford gate using only single-qubit Clifford gates as reference.@en

Randomized benchmarking (RB) is an efficient and robust method to characterize gate errors in quantum circuits. Averaging over random sequences of gates leads to estimates of gate errors in terms of the average fidelity. These estimates are isolated from the state preparation and measurement errors that plague other methods such as channel tomography and direct fidelity estimation. A decisive factor in the feasibility of randomized benchmarking is the number of sampled sequences required to obtain rigorous confidence intervals. Previous bounds were either prohibitively loose or required the number of sampled sequences to scale exponentially with the number of qubits in order to obtain a fixed confidence interval at a fixed error rate. Here, we show that, with a small adaptation to the randomized benchmarking procedure, the number of sampled sequences required for a fixed confidence interval is dramatically smaller than could previously be justified. In particular, we show that the number of sampled sequences required is essentially independent of the number of qubits and scales favorably with the average error rate of the system under investigation. We also investigate the fitting procedure inherent to randomized benchmarking in light of our results and find that standard methods such as ordinary least squares optimization can give misleading results. We therefore recommend moving to more sophisticated fitting methods such as iteratively reweighted least squares optimization. Our results bring rigorous randomized benchmarking on systems with many qubits into the realm of experimental feasibility.@en

Current techniques in quantum process tomography typically return a single point estimate of an unknown process based on a finite albeit large amount of measurement data. Due to statistical fluctuations, however, other processes close to the point estimate can also produce the observed data with near certainty. Unless appropriate error bars can be constructed, the point estimate does not carry any sound operational interpretation. Here, we provide a solution to this problem by constructing a confidence region estimator for quantum processes. Our method enables reliable estimation of essentially any figure of merit for quantum processes on few qubits, including the diamond distance to a specific noise model, the entanglement fidelity, and the worst-case entanglement fidelity, by identifying error regions which contain the true state with high probability. We also provide a software package, QPtomographer, implementing our estimator for the diamond norm and the worst-case entanglement fidelity. We illustrate its usage and performance with several simulated examples. Our tools can be used to reliably certify the performance of, e.g., error correction codes, implementations of unitary gates, or more generally any noise process affecting a quantum system.@en

The spin states of single electrons in gate-defined quantum dots satisfy crucial requirements for a practical quantum computer. These include extremely long coherence times, high-fidelity quantum operation, and the ability to shuttle electrons as a mechanism for on-chip flying qubits. To increase the number of qubits to the thousands or millions of qubits needed for practical quantum information, we present an architecture based on shared control and a scalable number of lines. Crucially, the control lines define the qubit grid, such that no local components are required. Our design enables qubit coupling beyond nearest neighbors, providing prospects for nonplanar quantum error correction protocols. Fabrication is based on a three-layer design to define qubit and tunnel barrier gates. We show that a double stripline on top of the structure can drive high-fidelity single-qubit rotations. Self-aligned inhomogeneous magnetic fields induced by direct currents through superconducting gates enable qubit addressability and readout. Qubit coupling is based on the exchange interaction, and we show that parallel two-qubit gates can be performed at the detuning-noise insensitive point. While the architecture requires a high level of uniformity in the materials and critical dimensions to enable shared control, it stands out for its simplicity and provides prospects for large-scale quantum computation in the near future.@en

Quantum communication has demonstrated its usefulness for quantum cryptography far beyond quantum key distribution. One domain is two-party cryptography, whose goal is to allow two parties who may not trust each other to solve joint tasks. Another interesting application is position-based cryptography whose goal is to use the geographical location of an entity as its only identifying credential. Unfortunately, security of these protocols is not possible against an all powerful adversary. However, if we impose some realistic physical constraints on the adversary, there exist protocols for which security can be proven, but these so far relied on the knowledge of the quantum operations performed during the protocols. In this work we improve the device-independent security proofs of Kaniewski and Wehner [New J. Phys. 18, 055004 (2016)NJOPFM1367-263010.1088/1367-2630/18/5/055004] for two-party cryptography (with memoryless devices) and we add a security proof for device-independent position verification (also memoryless devices) under different physical constraints on the adversary. We assess the quality of the devices by observing a Bell violation, and, as for Kaniewski and Wehner [New J. Phys. 18, 055004 (2016)NJOPFM1367-263010.1088/1367-2630/18/5/055004], security can be attained for any violation of the Clauser-Holt-Shimony-Horne inequality.@en

Quantum communication has demonstrated its usefulness for quantum cryptography far beyond quantum key distribution. One domain is two-party cryptography, whose goal is to allow two parties who may not trust each other to solve joint tasks. Another interesting application is position-based cryptography whose goal is to use the geographical location of an entity as its only identifying credential. Unfortunately, security of these protocols is not possible against an all powerful adversary. However, if we impose some realistic physical constraints on the adversary, there exist protocols for which security can be proven, but these so far relied on the knowledge of the quantum operations performed during the protocols. In this work we improve the device-independent security proofs of Kaniewski and Wehner [New J. Phys. 18, 055004 (2016)NJOPFM1367-263010.1088/1367-2630/18/5/055004] for two-party cryptography (with memoryless devices) and we add a security proof for device-independent position verification (also memoryless devices) under different physical constraints on the adversary. We assess the quality of the devices by observing a Bell violation, and, as for Kaniewski and Wehner [New J. Phys. 18, 055004 (2016)NJOPFM1367-263010.1088/1367-2630/18/5/055004], security can be attained for any violation of the Clauser-Holt-Shimony-Horne inequality.@en