Search

Recent completeness results on the ZX-Calculus used a third-party language, namely the ZW-Calculus. As a consequence, these proofs are elegant, but sadly non-constructive. We address this issue in the following. To do so, we first describe a generic normal form for ZX-diagrams in any fragment that contains Clifford+T quantum mechanics. We give sufficient conditions for an axiomatisation to be complete, and an algorithm to reach the normal form. Finally, we apply these results to the Clifford+T fragment and the general ZX-Calculus -- for which we already know the completeness--, but also for any fragment of rational angles: we show that the axiomatisation for Clifford+T is also complete for any fragment of dyadic angles, and that a simple new rule (called cancellation) is necessary and sufficient otherwise.

The ZX-Calculus is a graphical language for quantum mechanics. An axiomatisation has recently been proven to be complete for an approximatively universal fragment of quantum mechanics, the so-called Clifford+T fragment. We focus here on the expressive power of this axiomatisation beyond Clifford+T Quantum mechanics. We consider the full pure qubit quantum mechanics, and mainly prove two results: (i) First, the axiomatisation for Clifford+T quantum mechanics is also complete for all equations involving some kind of linear diagrams. The linearity of the diagrams reflects the phase group structure, an essential feature of the ZX-calculus. In particular all the axioms of the ZX-calculus are involving linear diagrams. (ii) We also show that the axiomatisation for Clifford+T is not complete in general but can be completed by adding a single (non linear) axiom, providing a simpler axiomatisation of the ZX-calculus for pure quantum mechanics than the one recently introduced by Ng&Wang.

The stabilizer ZX-calculus is a rigorous graphical language for reasoning about quantum mechanics. The language is sound and complete: one can transform a stabilizer ZX-diagram into another one using the graphical rewrite rules if and only if these two diagrams represent the same quantum evolution or quantum state. We previously showed that the stabilizer ZX-calculus can be simplified by reducing the number of rewrite rules, without losing the property of completeness [Backens, Perdrix & Wang, EPTCS 236:1--20, 2017]. Here, we show that most of the remaining rules of the language are indeed necessary. We do however leave as an open question the necessity of two rules. These include, surprisingly, the bialgebra rule, which is an axiomatisation of complementarity, the cornerstone of the ZX-calculus. Furthermore, we show that a weaker ambient category -- a braided autonomous category instead of the usual compact closed category -- is sufficient to recover the meta rule 'only connectivity matters', even without assuming any symmetries of the generators.

We introduce the first complete and approximatively universal diagrammatic language for quantum mechanics. We make the ZX-Calculus, a diagrammatic language introduced by Coecke and Duncan, complete for the so-called Clifford+T quantum mechanics by adding four new axioms to the language. The completeness of the ZX-Calculus for Clifford+T quantum mechanics was one of the main open questions in categorical quantum mechanics. We prove the completeness of the Clifford+T fragment of the ZX-Calculus using the recently studied ZW-Calculus, a calculus dealing with integer matrices. We also prove that the Clifford+T fragment of the ZX-Calculus represents exactly all the matrices over some finite dimensional extension of the ring of dyadic rationals.

An important class of contextuality arguments in quantum foundations are the All-versus-Nothing (AvN) proofs, generalising a construction originally due to Mermin. We present a general formulation of All-versus-Nothing arguments, and a complete characterisation of all such arguments which arise from stabiliser states. We show that every AvN argument for an n-qubit stabiliser state can be reduced to an AvN proof for a three-qubit state which is local Clifford-equivalent to the tripartite GHZ state. This is achieved through a combinatorial characterisation of AvN arguments, the AvN triple Theorem, whose proof makes use of the theory of graph states. This result enables the development of a computational method to generate all the AvN arguments in $\mathbb{Z}_2$ on n-qubit stabiliser states. We also present new insights into the stabiliser formalism and its connections with logic., Comment: 18 pages, 6 figures

The ZX-Calculus is a powerful graphical language for quantum mechanics and quantum information processing. The completeness of the language -- i.e. the ability to derive any true equation -- is a crucial question. In the quest of a complete ZX-calculus, supplementarity has been recently proved to be necessary for quantum diagram reasoning (MFCS 2016). Roughly speaking, supplementarity consists in merging two subdiagrams when they are parameterized by antipodal angles. We introduce a generalised supplementarity -- called cyclotomic supplementarity -- which consists in merging n subdiagrams at once, when the n angles divide the circle into equal parts. We show that when n is an odd prime number, the cyclotomic supplementarity cannot be derived, leading to a countable family of new axioms for diagrammatic quantum reasoning.We exhibit another new simple axiom that cannot be derived from the existing rules of the ZX-Calculus, implying in particular the incompleteness of the language for the so-called Clifford+T quantum mechanics. We end up with a new axiomatisation of an extended ZX-Calculus, including an axiom schema for the cyclotomic supplementarity., Comment: Mathematical Foundations of Computer Science, Aug 2017, Aalborg, Denmark

We introduce a ZX-like diagrammatic language devoted to manipulating real matrices - and rebits -, with its own set of axioms. We prove the necessity of some non trivial axioms of these. We show that some restriction of the language is complete. We exhibit two interpretations to and from the ZX-Calculus, thus showing the consistency between the two languages. Finally, we derive from our work a way to extract the real or imaginary part of a ZX-diagram, and prove that a restriction of our language is complete if the equivalent restriction of the ZX-calculus is complete., Comment: In Proceedings QPL 2017, arXiv:1802.09737

Measurement-based quantum computing (MBQC) is a universal model for quantum computation. The combinatorial characterisation of determinism in this model, powered by measurements, and hence, fundamentally probabilistic, is the cornerstone of most of the breakthrough results in this field. The most general known sufficient condition for a deterministic MBQC to be driven is that the underlying graph of the computation has a particular kind of flow called Pauli flow. The necessity of the Pauli flow was an open question. We show that the Pauli flow is necessary for real-MBQC, and not in general providing counterexamples for (complex) MBQC. We explore the consequences of this result for real MBQC and its applications. Real MBQC and more generally real quantum computing is known to be universal for quantum computing. Real MBQC has been used for interactive proofs by McKague. The two-prover case corresponds to real-MBQC on bipartite graphs. While (complex) MBQC on bipartite graphs are universal, the universality of real MBQC on bipartite graphs was an open question. We show that real bipartite MBQC is not universal proving that all measurements of real bipartite MBQC can be parallelised leading to constant depth computations. As a consequence, McKague techniques cannot lead to two-prover interactive proofs.

Analyzing pseudo-telepathy graph games, we propose a way to build contextuality scenarios exhibiting the quantum supremacy using graph states. We consider the combinatorial structures that generate equivalent scenarios. We introduce a new tool called multipartiteness width to investigate which scenarios are harder to decompose and show that there exist graphs generating scenarios with a linear multipartiteness width.

The stabilizer ZX-calculus is a rigorous graphical language for reasoning about quantum mechanics.The language is sound and complete: a stabilizer ZX-diagram can be transformed into another one if and only if these two diagrams represent the same quantum evolution or quantum state. We show that the stabilizer ZX-calculus can be simplified, removing unnecessary equations while keeping only the essential axioms which potentially capture fundamental structures of quantum mechanics. We thus give a significantly smaller set of axioms and prove that meta-rules like 'colour symmetry' and 'upside-down symmetry', which were considered as axioms in previous versions of the language, can in fact be derived. In particular, we show that the additional symbol and one of the rules which had been recently introduced to keep track of scalars (diagrams with no inputs or outputs) are not necessary., Comment: In Proceedings QPL 2016, arXiv:1701.00242

The ZX-calculus is a powerful diagrammatic language for quantum mechanics and quantum information processing. We prove that its \pi/4-fragment is not complete, in other words the ZX-calculus is not complete for the so called "Clifford+T quantum mechanics". The completeness of this fragment was one of the main open problems in categorical quantum mechanics, a programme initiated by Abramsky and Coecke. The ZX-calculus was known to be incomplete for quantum mechanics. On the other hand, its \pi/2-fragment is known to be complete, i.e. the ZX-calculus is complete for the so called "stabilizer quantum mechanics". Deciding whether its \pi/4-fragment is complete is a crucial step in the development of the ZX-calculus since this fragment is approximately universal for quantum mechanics, contrary to the \pi/2-fragment. To establish our incompleteness result, we consider a fairly simple property of quantum states called supplementarity. We show that supplementarity can be derived in the ZX-calculus if and only if the angles involved in this equation are multiples of \pi/2. In particular, the impossibility to derive supplementarity for \pi/4 implies the incompleteness of the ZX-calculus for Clifford+T quantum mechanics. As a consequence, we propose to add the supplementarity to the set of rules of the ZX-calculus. We also show that if a ZX-diagram involves antiphase twins, they can be merged when the ZX-calculus is augmented with the supplementarity rule. Merging antiphase twins makes diagrammatic reasoning much easier and provides a purely graphical meaning to the supplementarity rule., Comment: Generalised proof and graphical interpretation. 16 pages, submitted

The local minimum degree of a graph is the minimum degree that can be reached by means of local complementation. For any n, there exist graphs of order n which have a local minimum degree at least 0.189n, or at least 0.110n when restricted to bipartite graphs. Regarding the upper bound, we show that for any graph of order n, its local minimum degree is at most 3n/8+o(n) and n/4+o(n) for bipartite graphs, improving the known n/2 upper bound. We also prove that the local minimum degree is smaller than half of the vertex cover number (up to a logarithmic term). The local minimum degree problem is NP-Complete and hard to approximate. We show that this problem, even when restricted to bipartite graphs, is in W[2] and FPT-equivalent to the EvenSet problem, which W[1]-hardness is a long standing open question. Finally, we show that the local minimum degree is computed by a O*(1.938^n)-algorithm, and a O*(1.466^n)-algorithm for the bipartite graphs.

When applied on some particular quantum entangled states, measurements are universal for quantum computing. In particular, despite the fondamental probabilistic evolution of quantum measurements, any unitary evolution can be simulated by a measurement-based quantum computer (MBQC). We consider the extended version of the MBQC where each measurement can occur not only in the (X,Y)-plane of the Bloch sphere but also in the (X,Z)- and (Y,Z)-planes. The existence of a gflow in the underlying graph of the computation is a necessary and sufficient condition for a certain kind of determinism. We extend the focused gflow (a gflow in a particular normal form) defined for the (X,Y)-plane to the extended case, and we provide necessary and sufficient conditions for the existence of such normal forms.

Causal Graph Dynamics extend Cellular Automata to arbitrary, bounded-degree, time-varying graphs. The whole graph evolves in discrete time steps, and this global evolution is required to have a number of physics-like symmetries: shift-invariance (it acts everywhere the same) and causality (information has a bounded speed of propagation). We add a further physics-like symmetry, namely reversibility. KEYWORDS: Bijective, invertible, injective, surjective, one-to-one, onto, Cayley graphs, Hedlund, Block representation, Lattice-gas automaton, Reversible Cellular Automata., Comment: 33 pages, 10 figures