Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols.
Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols.
From both intuitive and physical perspectives, it is generally recognized that within a resource theory framework, free operations cannot broadcast a resource state due to their inability to generate resource from free states. In the stabilizer formalism of fault-tolerant quantum computation, the basic ingredients of the corresponding resource theory consist of stabilizer states as free states and stabilizer operations as free operations. The celebrated Gottesman-Knill theorem shows that quantum advantages over classical computation come from the magic (nonstabilizer) resource, such as magic states or non-Clifford gates. In this work, we prove that broadcasting of any magic state via stabilizer operations is impossible, which is reminiscent of the no-broadcasting theorems for noncommuting states or quantum correlations. We further derive a trade-off relation between the magic resource consumed in the initial system and that gained in the target system. These results characterize magic states in the stabilizer formalism from the broadcasting angle, and may have implications for distributed quantum computation and quantum secret sharing.
We study the computational power of unitary Clifford circuits with solely magic state inputs (CM circuits), supplemented by classical efficient computation. We show that CM circuits are hard to classically simulate up to multiplicative error (assuming polynomial hierarchy non-collapse), and also up to additive error under plausible average-case hardness conjectures. Unlike other such known classes, a broad variety of possible conjectures apply. Along the way, we give an extension of the Gottesman-Knill theorem that applies to universal computation, showing that for Clifford circuits with joint stabilizer and non-stabilizer inputs, the stabilizer part can be eliminated in favour of classical simulation, leaving a Clifford circuit on only the non-stabilizer part. Finally, we discuss implementational advantages of CM circuits.
The stabiliser formalism is a widely used and successful subtheory of quantum mechanics consisting of stabiliser states, Clifford unitaries and Pauli measurements. The power of the formalism comes from the description of its elements via simple group theory. Although the origins of the formalism lie in quantum error correction and fault-tolerant quantum computing, the utility of the formalism goes beyond that. The Gottesman-Knill theorem states that the dynamics of stabiliser states under Clifford unitaries and Pauli measurements can be efficiently simulated on a classical computer. This algorithm can be extended to arbitrary states and unitaries in multiple ways at the cost of an increased runtime. This runtime can be seen as a quantification of the non-stabiliser resources needed to implement a quantum circuit. Moreover, as non-stabiliser elements are necessary for universal quantum computing, the runtime provides a way to measure the “non-classicality” of a computation. This is particularly pronounced in the magic state model of quantum computing where the only non-stabiliser elements are given by magic states. Hence, in the resource theory of magic, resources are measured through magic monotones which are operationally linked to runtimes of classical simulation algorithms. In this thesis, I discuss different aspects of the resource theory of magic. The mentioned classical simulation algorithms require the computation of magic monotones which is in general a computationally intractable problem. However, I show that the computational complexity can be exponentially reduced for certain classes of symmetric states, such as copies of magic states. To this end, the symmetries of the convex hull of stabiliser states are characterised and linked to their properties as so-called designs. In addition, I study the recently introduced class of completely stabiliser-preserving channels (CSP), which is the class of quantum channels unable to generate magic resources. It is shown that this class is strictly larger than the class of stabiliser operations, composed of Clifford unitaries and Pauli measurements. This finding could have several interesting consequences. First, it implies that there is a class of efficiently simulable quantum channels beyond the Gottesman-Knill theorem. Second, it is possible that optimal magic state distillation rates cannot be achieved via stabiliser operations and this gap is in fact significant. Further applications of the stabiliser formalism come through design theory. A unitary t-design is an ensemble of unitaries which reproduce the first t moments of the Haar measure on the unitary group. Randomness in the form of Haar-random unitaries is an essential building block in many quantum information protocols. Implementing such Haar-random unitaries is however often impractical. Here, designs can exhibit considerably lower resource requirements while still being random enough for most applications. Some of the most prominent examples of such protocols concern the certification and characterisation of quantum systems, such as randomised benchmarking. Interestingly, the group of Clifford unitaries forms a unitary 3-design and is often the prime choice thanks to efficient group operations. In this thesis, I summarise my recent results obtained with collaborators in constructing approximate unitary t-designs from the Clifford group supplemented by only few non-Clifford gates. Intriguingly, this construction uses only O(t^4) single qubit non-Clifford gates and is independent of the number of qubits n. Overall, this yields a gate count which is a significant improvement over for the Brandao-Harrow- Horodecki construction based on local random circuits. To provide context for this result, I review the representation theory of the Clifford group and define the Clifford semigroup. In an attempt to generalise approximations results for the unitary group to the Clifford group, the Clifford semigroup is investigated for suitable approximations of the Clifford twirl.
Stabilizer operations (SO) occupy a prominent role in fault-tolerant quantum computing. They are defined operationally by the use of Clifford gates, Pauli measurements, and classical control. These operations can be efficiently simulated on a classical computer, a result which is known as the Gottesman–Knill theorem. However, an additional supply of magic states is enough to promote them to a universal, fault-tolerant model for quantum computing. To quantify the needed resources in terms of magic states, a resource theory of magic has been developed. SO are considered free within this theory; however, they are not the most general class of free operations. From an axiomatic point of view, these are the completely stabilizer-preserving (CSP) channels, defined as those that preserve the convex hull of stabilizer states. It has been an open problem to decide whether these two definitions lead to the same class of operations. In this work, we answer this question in the negative, by constructing an explicit counter-example. This indicates that recently proposed stabilizer-based simulation techniques of CSP maps are strictly more powerful than Gottesman–Knill-like methods. The result is analogous to a well-known fact in entanglement theory, namely, that there is a gap between the operationally defined class of local operations and classical communication and the axiomatically defined class of separable channels.
In communication complexity, a number of distant parties have the task of calculating a distributed function of their inputs, while minimizing the amount of communication between them. It is known that with quantum resources, such as entanglement and quantum channels, one can obtain significant reductions in the communication complexity of some tasks. In this work, we study the role of the quantum superposition of the direction of communication as a resource for communication complexity. We present a tripartite communication task for which such a superposition allows for an exponential saving in communication, compared to one-way quantum (or classical) communication; the advantage also holds when we allow for protocols with bounded error probability.
Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.