BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Simon Perdrix

Simon Perdrix appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phLogic in Computer ScienceComputational Complexitymath.CODiscrete MathematicsInformation Theorymath-phmath.CTmath.ITmath.MP

Catalog footprint

What is connected

34works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

34 published item(s)

preprint2026arXiv

Diagrammatic Reasoning with Control as a Constructor, Applications to Quantum Circuits

Control is a fundamental concept in quantum and reversible computational models. It enables the conditional application of a transformation to a system, depending on the state of another system. We introduce a general framework for diagrammatic reasoning featuring control as a constructor. To this end, we provide an elementary axiomatisation of control functors, extending the standard formalism of props to controlled props. As an application, we show that controlled props facilitate diagrammatic reasoning for quantum circuits by introducing a simple and complete set of relations involving at most three qubits, whereas in the standard prop setting any complete axiomatisation necessarily requires relations acting on arbitrarily many qubits.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Coherent control and distinguishability of quantum channels via PBS-diagrams

We introduce a graphical language for coherent control of general quantum channels inspired by practical quantum optical setups involving polarising beam splitters (PBS). As standard completely positive trace preserving maps are known not to be appropriate to represent coherently controlled quantum channels, we propose to instead use purified channels, an extension of Stinespring's dilation. We characterise the observational equivalence of purified channels in various coherent-control contexts, paving the way towards a faithful representation of quantum channels under coherent control.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Hybrid quantum-classical circuit simplification with the ZX-calculus

We present a complete optimization procedure for hybrid quantum-classical circuits with classical parity logic. While common optimization techniques for quantum algorithms focus on rewriting solely the pure quantum segments, there is interest in applying a global optimization process for applications such as quantum error correction and quantum assertions. This work, based on the pure-quantum circuit optimization procedure by Duncan et al., uses an extension of the formal graphical ZX-calculus called ZX-ground as an intermediary representation of the hybrid circuits to allow for granular optimizations below the quantum-gate level. We define a translation from hybrid circuits into diagrams that admit the graph-theoretical focused-gFlow property, needed for the final extraction back into a circuit. We then derive a number of gFlow-preserving optimization rules for ZX-ground diagrams that reduce the size of the graph, and devise an strategy to find optimization opportunities by rewriting the diagram guided by a Gauss elimination process. Then, after extracting the circuit, we present a general procedure for detecting segments of circuit-like ZX-ground diagrams which can be implemented with classical gates in the extracted circuit. We have implemented our optimization procedure as an extension to the open-source python library PyZX.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Colored props for large scale graphical reasoning

The prop formalism allows representation of processes withstring diagrams and has been successfully applied in various areas such as quantum computing, electric circuits and control flow graphs. However, these graphical approaches suffer from scalability problems when it comes to writing large diagrams. A proposal to tackle this issue has been investigated for ZX-calculus using colored props. This paper extends the approach to any prop, making it a general tool for graphical languages manipulation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus

We present a completely new approach to quantum circuit optimisation, based on the ZX-calculus. We first interpret quantum circuits as ZX-diagrams, which provide a flexible, lower-level language for describing quantum computations graphically. Then, using the rules of the ZX-calculus, we give a simplification strategy for ZX-diagrams based on the two graph transformations of local complementation and pivoting and show that the resulting reduced diagram can be transformed back into a quantum circuit. While little is known about extracting circuits from arbitrary ZX-diagrams, we show that the underlying graph of our simplified ZX-diagram always has a graph-theoretic property called generalised flow, which in turn yields a deterministic circuit extraction procedure. For Clifford circuits, this extraction procedure yields a new normal form that is both asymptotically optimal in size and gives a new, smaller upper bound on gate depth for nearest-neighbour architectures. For Clifford+T and more general circuits, our technique enables us to to `see around' gates that obstruct the Clifford structure and produce smaller circuits than naive 'cut-and-resynthesise' methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Pauli Fusion: a Computational Model to Realise Quantum Transformations from ZX Terms

We present an abstract model of quantum computation, the "Pauli Fusion" model, whose primitive operations correspond closely to generators of the ZX calculus (a formal graphical language for quantum computing). The fundamental operations of Pauli Fusion are also straightforward abstractions of basic processes in some leading proposed quantum technologies. These operations have non-deterministic heralded effects, similarly to measurement-based quantum computation. We describe sufficient conditions for Pauli Fusion procedures to be deterministically realisable, so that it performs a given transformation independently of its non-deterministic outcomes. This provides an operational model to realise ZX terms beyond the circuit model.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations

We introduce the PBS-calculus to represent and reason on quantum computations involving coherent control of quantum operations. Coherent control, and in particular indefinite causal order, is known to enable multiple computational and communication advantages over classically ordered models like quantum circuits. The PBS-calculus is inspired by quantum optics, in particular the polarising beam splitter (PBS for short). We formalise the syntax and the semantics of the PBS-diagrams, and we equip the language with an equational theory, which is proved to be sound and complete: two diagrams are representing the same quantum evolution if and only if one can be transformed into the other using the rules of the PBS-calculus. Moreover, we show that the equational theory is minimal. Finally, we consider applications like the implementation of controlled permutations and the unrolling of loops.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

SZX-calculus: Scalable Graphical Quantum Reasoning

We introduce the Scalable ZX-calculus (SZX-calculus for short), a formal and compact graphical language for the design and verification of quantum computations. The SZX-calculus is an extension of the ZX-calculus, a powerful framework that captures graphically the fundamental properties of quantum mechanics through its complete set of rewrite rules. The ZX-calculus is, however, a low level language, with each wire representing a single qubit. This limits its ability to handle large and elaborate quantum evolutions. We extend the ZX-calculus to registers of qubits and allow compact representation of sub-diagrams via binary matrices. We show soundness and completeness of the SZX-calculus and provide two examples of applications, for graph states and error correcting codes.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

A complete characterisation of All-versus-Nothing arguments for stabiliser states

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.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

A Simplified Stabilizer ZX-calculus

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.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Contextuality in multipartite pseudo-telepathy graph games

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Supplementarity is Necessary for Quantum Diagram Reasoning

The ZX-calculus is a powerful diagrammatic language for quantum mechanics and quantum information processing. We prove that its π/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 π/2-fragment is known to be complete, i.e. the ZX-calculus is complete for the so called "stabilizer quantum mechanics". Deciding whether its π/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 π/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 π/2. In particular, the impossibility to derive supplementarity for π/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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parametrized Complexity of Weak Odd Domination Problems

Given a graph $G=(V,E)$, a subset $B\subseteq V$ of vertices is a weak odd dominated (WOD) set if there exists $D \subseteq V {\setminus} B$ such that every vertex in $B$ has an odd number of neighbours in $D$. $κ(G)$ denotes the size of the largest WOD set, and $κ'(G)$ the size of the smallest non-WOD set. The maximum of $κ(G)$ and $|V|-κ'(G)$, denoted $κ_Q(G)$, plays a crucial role in quantum cryptography. In particular deciding, given a graph $G$ and $k>0$, whether $κ_Q(G)\le k$ is of practical interest in the design of graph-based quantum secret sharing schemes. The decision problems associated with the quantities $κ$, $κ'$ and $κ_Q$ are known to be NP-Complete. In this paper, we consider the approximation of these quantities and the parameterized complexity of the corresponding problems. We mainly prove the fixed-parameter intractability (W$[1]$-hardness) of these problems. Regarding the approximation, we show that $κ_Q$, $κ$ and $κ'$ admit a constant factor approximation algorithm, and that $κ$ and $κ'$ have no polynomial approximation scheme unless P=NP.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Reversibility in the Extended Measurement-based Quantum Computation

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Parameterized Complexity of Domination-type Problems and Application to Linear Codes

We study the parameterized complexity of domination-type problems. (sigma,rho)-domination is a general and unifying framework introduced by Telle: a set D of vertices of a graph G is (sigma,rho)-dominating if for any v in D, |N(v)\cap D| in sigma and for any $v\notin D, |N(v)\cap D| in rho. We mainly show that for any sigma and rho the problem of (sigma,rho)-domination is W[2] when parameterized by the size of the dominating set. This general statement is optimal in the sense that several particular instances of (sigma,rho)-domination are W[2]-complete (e.g. Dominating Set). We also prove that (sigma,rho)-domination is W[2] for the dual parameterization, i.e. when parameterized by the size of the dominated set. We extend this result to a class of domination-type problems which do not fall into the (sigma,rho)-domination framework, including Connected Dominating Set. We also consider problems of coding theory which are related to domination-type problems with parity constraints. In particular, we prove that the problem of the minimal distance of a linear code over Fq is W[2] for both standard and dual parameterizations, and W[1]-hard for the dual parameterization. To prove W[2]-membership of the domination-type problems we extend the Turing-way to parameterized complexity by introducing a new kind of non deterministic Turing machine with the ability to perform `blind' transitions, i.e. transitions which do not depend on the content of the tapes. We prove that the corresponding problem Short Blind Multi-Tape Non-Deterministic Turing Machine is W[2]-complete. We believe that this new machine can be used to prove W[2]-membership of other problems, not necessarily related to domination

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Call-by-value, call-by-name and the vectorial behaviour of the algebraic λ-calculus

We examine the relationship between the algebraic lambda-calculus, a fragment of the differential lambda-calculus and the linear-algebraic lambda-calculus, a candidate lambda-calculus for quantum computation. Both calculi are algebraic: each one is equipped with an additive and a scalar-multiplicative structure, and their set of terms is closed under linear combinations. However, the two languages were built using different approaches: the former is a call-by-name language whereas the latter is call-by-value; the former considers algebraic equalities whereas the latter approaches them through rewrite rules. In this paper, we analyse how these different approaches relate to one another. To this end, we propose four canonical languages based on each of the possible choices: call-by-name versus call-by-value, algebraic equality versus algebraic rewriting. We show that the various languages simulate one another. Due to subtle interaction between beta-reduction and algebraic rewriting, to make the languages consistent some additional hypotheses such as confluence or normalisation might be required. We carefully devise the required properties for each proof, making them general enough to be valid for any sub-language satisfying the corresponding properties.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Pivoting makes the ZX-calculus complete for real stabilizers

We show that pivoting property of graph states cannot be derived from the axioms of the ZX-calculus, and that pivoting does not imply local complementation of graph states. Therefore the ZX-calculus augmented with pivoting is strictly weaker than the calculus augmented with the Euler decomposition of the Hadamard gate. We derive an angle-free version of the ZX-calculus and show that it is complete for real stabilizer quantum mechanics.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quantum Circuits for the Unitary Permutation Problem

We consider the Unitary Permutation problem which consists, given $n$ unitary gates $U_1, \ldots, U_n$ and a permutation $σ$ of $\{1,\ldots, n\}$, in applying the unitary gates in the order specified by $σ$, i.e. in performing $U_{σ(n)}\ldots U_{σ(1)}$. This problem has been introduced and investigated by Colnaghi et al. where two models of computations are considered. This first is the (standard) model of query complexity: the complexity measure is the number of calls to any of the unitary gates $U_i$ in a quantum circuit which solves the problem. The second model provides quantum switches and treats unitary transformations as inputs of second order. In that case the complexity measure is the number of quantum switches. In their paper, Colnaghi et al. have shown that the problem can be solved within $n^2$ calls in the query model and $\frac{n(n-1)}2$ quantum switches in the new model. We refine these results by proving that $n\log_2(n) +Θ(n)$ quantum switches are necessary and sufficient to solve this problem, whereas $n^2-2n+4$ calls are sufficient to solve this problem in the standard quantum circuit model. We prove, with an additional assumption on the family of gates used in the circuits, that $n^2-o(n^{7/4+ε})$ queries are required, for any $ε>0$. The upper and lower bounds for the standard quantum circuit model are established by pointing out connections with the permutation as substring problem introduced by Karp.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Access structure in graphs in high dimension and application to secret sharing

We give graphical characterisation of the access structure to both classical and quantum information encoded onto a multigraph defined for prime dimension $q$, as well as explicit decoding operations for quantum secret sharing based on graph state protocols. We give a lower bound on $k$ for the existence of a $((k,n))_q$ scheme and prove, using probabilistic methods, that there exists $α$ such that a random multigraph has an accessing parameter $k\leq αn$ with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Completeness of algebraic CPS simulations

The algebraic lambda calculus and the linear algebraic lambda calculus are two extensions of the classical lambda calculus with linear combinations of terms. They arise independently in distinct contexts: the former is a fragment of the differential lambda calculus, the latter is a candidate lambda calculus for quantum computation. They differ in the handling of application arguments and algebraic rules. The two languages can simulate each other using an algebraic extension of the well-known call-by-value and call-by-name CPS translations. These simulations are sound, in that they preserve reductions. In this paper, we prove that the simulations are actually complete, strengthening the connection between the two languages.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Environment and classical channels in categorical quantum mechanics

We present a both simple and comprehensive graphical calculus for quantum computing. In particular, we axiomatize the notion of an environment, which together with the earlier introduced axiomatic notion of classical structure enables us to define classical channels, quantum measurements and classical control. If we moreover adjoin the earlier introduced axiomatic notion of complementarity, we obtain sufficient structural power for constructive representation and correctness derivation of typical quantum informatic protocols.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Graph States, Pivot Minor, and Universality of (X,Z)-measurements

The graph state formalism offers strong connections between quantum information processing and graph theory. Exploring these connections, first we show that any graph is a pivot-minor of a planar graph, and even a pivot minor of a triangular grid. Then, we prove that the application of measurements in the (X,Z)-plane over graph states represented by triangular grids is a universal measurement-based model of quantum computation. These two results are in fact two sides of the same coin, the proof of which is a combination of graph theoretical and quantum information techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Minimum Degree up to Local Complementation: Bounds and Complexity

The local minimum degree of a graph is the minimum degree reached by means of a series of local complementations. In this paper, we investigate on this quantity which plays an important role in quantum computation and quantum error correcting codes. First, we show that the local minimum degree of the Paley graph of order p is greater than sqrt{p} - 3/2, which is, up to our knowledge, the highest known bound on an explicit family of graphs. Probabilistic methods allows us to derive the existence of an infinite number of graphs whose local minimum degree is linear in their order with constant 0.189 for graphs in general and 0.110 for bipartite graphs. As regards the computational complexity of the decision problem associated with the local minimum degree, we show that it is NP-complete and that there exists no k-approximation algorithm for this problem for any constant k unless P = NP.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Weak Odd Domination and Graph-based Quantum Secret Sharing

A weak odd dominated (WOD) set in a graph is a subset B of vertices for which there exists a distinct set of vertices C such that every vertex in B has an odd number of neighbors in C. We point out the connections of weak odd domination with odd domination, [sigma,rho]-domination, and perfect codes. We introduce bounds on κ(G), the maximum size of WOD sets of a graph G, and on κ'(G), the minimum size of non WOD sets of G. Moreover, we prove that the corresponding decision problems are NP-complete. The study of weak odd domination is mainly motivated by the design of graph-based quantum secret sharing protocols: a graph G of order n corresponds to a secret sharing protocol which threshold is κ_Q(G) = max(κ(G), n-κ'(G)). These graph-based protocols are very promising in terms of physical implementation, however all such graph-based protocols studied in the literature have quasi-unanimity thresholds (i.e. κ_Q(G)=n-o(n) where n is the order of the graph G underlying the protocol). In this paper, we show using probabilistic methods, the existence of graphs with smaller κ_Q (i.e. κ_Q(G)< 0.811n where n is the order of G). We also prove that deciding for a given graph G whether κ_Q(G)< k is NP-complete, which means that one cannot efficiently double check that a graph randomly generated has actually a κ_Q smaller than 0.811n.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Classical versus Quantum Graph-based Secret Sharing

We study a simple graph-based classical secret sharing scheme: every player's share consists of a random key together with the encryption of the secret with the keys of his neighbours. A characterisation of the authorised and forbidden sets of players is given. Moreover, we show that this protocol is equivalent to the graph state quantum secret sharing (GS-QSS) schemes when the secret is classical. When the secret is an arbitrary quantum state, a set of players is authorised for a GS-QSS scheme if and only if, for the corresponding simple classical graph-based protocol, the set is authorised and its complement set is not.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

New Protocols and Lower Bound for Quantum Secret Sharing with Graph States

We introduce a new family of quantum secret sharing protocols with limited quantum resources which extends the protocols proposed by Markham and Sanders and by Broadbent, Chouha, and Tapp. Parametrized by a graph G and a subset of its vertices A, the protocol consists in: (i) encoding the quantum secret into the corresponding graph state by acting on the qubits in A; (ii) use a classical encoding to ensure the existence of a threshold. These new protocols realize ((k,n)) quantum secret sharing i.e., any set of at least k players among n can reconstruct the quantum secret, whereas any set of less than k players has no information about the secret. In the particular case where the secret is encoded on all the qubits, we explore the values of k for which there exists a graph such that the corresponding protocol realizes a ((k,n)) secret sharing. We show that for any threshold k> n-n^{0.68} there exists a graph allowing a ((k,n)) protocol. On the other hand, we prove that for any k< 79n/156 there is no graph G allowing a ((k,n)) protocol. As a consequence there exists n_0 such that the protocols introduced by Markham and Sanders admit no threshold k when the secret is encoded on all the qubits and n>n_0.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimal accessing and non-accessing structures for graph protocols

An accessing set in a graph is a subset B of vertices such that there exists D subset of B, such that each vertex of V\B has an even number of neighbors in D. In this paper, we introduce new bounds on the minimal size kappa'(G) of an accessing set, and on the maximal size kappa(G) of a non-accessing set of a graph G. We show strong connections with perfect codes and give explicitly kappa(G) and kappa'(G) for several families of graphs. Finally, we show that the corresponding decision problems are NP-Complete.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Which graph states are useful for quantum information processing?

Graph states are an elegant and powerful quantum resource for measurement based quantum computation (MBQC). They are also used for many quantum protocols (error correction, secret sharing, etc.). The main focus of this paper is to provide a structural characterisation of the graph states that can be used for quantum information processing. The existence of a gflow (generalized flow) is known to be a requirement for open graphs (graph, input set and output set) to perform uniformly and strongly deterministic computations. We weaken the gflow conditions to define two new more general kinds of MBQC: uniform equiprobability and constant probability. These classes can be useful from a cryptographic and information point of view because even though we cannot do a deterministic computation in general we can preserve the information and transfer it perfectly from the inputs to the outputs. We derive simple graph characterisations for these classes and prove that the deterministic and uniform equiprobability classes collapse when the cardinalities of inputs and outputs are the same. We also prove the reversibility of gflow in that case. The new graphical characterisations allow us to go from open graphs to graphs in general and to consider this question: given a graph with no inputs or outputs fixed, which vertices can be chosen as input and output for quantum information processing? We present a characterisation of the sets of possible inputs and ouputs for the equiprobability class, which is also valid for deterministic computations with inputs and ouputs of the same cardinality.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Computational depth complexity of measurement-based quantum computation

We prove that one-way quantum computations have the same computational power as quantum circuits with unbounded fan-out. It demonstrates that the one-way model is not only one of the most promising models of physical realisation, but also a very powerful model of quantum computation. It confirms and completes previous results which have pointed out, for some specific problems, a depth separation between the one-way model and the quantum circuit model. Since one-way model has the same computational power as unbounded quantum fan-out circuits, the quantum Fourier transform can be approximated in constant depth in the one-way model, and thus the factorisation can be done by a polytime probabilistic classical algorithm which has access to a constant-depth one-way quantum computer. The extra power of the one-way model, comparing with the quantum circuit model, comes from its classical-quantum hybrid nature. We show that this extra power is reduced to the capability to perform unbounded classical parity gates in constant depth.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Graphs States and the necessity of Euler Decomposition

Coecke and Duncan recently introduced a categorical formalisation of the interaction of complementary quantum observables. In this paper we use their diagrammatic language to study graph states, a computationally interesting class of quantum states. We give a graphical proof of the fixpoint property of graph states. We then introduce a new equation, for the Euler decomposition of the Hadamard gate, and demonstrate that Van den Nest's theorem--locally equivalent graphs represent the same entanglement--is equivalent to this new axiom. Finally we prove that the Euler decomposition equation is not derivable from the existing axioms.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Classically-Controlled Quantum Computation

Quantum computations usually take place under the control of the classical world. We introduce a Classically-controlled Quantum Turing Machine (CQTM) which is a Turing Machine (TM) with a quantum tape for acting on quantum data, and a classical transition function for a formalized classical control. In CQTM, unitary transformations and measurements are allowed. We show that any classical TM is simulated by a CQTM without loss of efficiency. The gap between classical and quantum computations, already pointed out in the framework of measurement-based quantum computation is confirmed. To appreciate the similarity of programming classical TM and CQTM, examples are given.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Measurement-Based Quantum Turing Machines and Questions of Universalities

Quantum measurement is universal for quantum computation. This universality allows alternative schemes to the traditional three-step organisation of quantum computation: initial state preparation, unitary transformation, measurement. In order to formalize these other forms of computation, while pointing out the role and the necessity of classical control in measurement-based computation, and for establishing a new upper bound of the minimal resources needed to quantum universality, a formal model is introduced by means of Measurement-based Quantum Turing Machines.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

State Transfer instead of Teleportation in Measurement-based Quantum Computation

Quantum measurement is universal for quantum computation. The model of quantum computation introduced by Nielsen and further developed by Leung relies on a generalized form of teleportation. In order to simulate any n-qubit unitary transformation with this model, 4 auxiliary qubits are required. Moreover Leung exhibited a universal family of observables composed of 4 two-qubit measurements. We introduce a model of quantum computation via measurements only, relying on state transfer: state transfer only retains the part of teleportation which is necessary for computating. In order to simulate any n-qubit unitary transformation with this new model, only one auxiliary qubit is required. Moreover we exhibit a universal family of observables composed of 3 one-qubit measurements and only one two-qubit measurement. This model improves those of Nielsen and Leung in terms of both the number of auxiliary qubits and the number of two-qubit measurements required for quantum universality. In both cases, the minimal amounts of necessary resources are now reached: one auxiliary qubit (because measurement is destructive) and one two-qubit measurement (for creating entanglement).

0 citations0 reviewsNo code linkedOpen access