Niel de Beaudrap
Niel de Beaudrap
Wolfson Building, Parks Road, Oxford OX1 3QD
Interests
I am interested in quantum computation, and its relationship to theoretical computer science generally. In particular, I am interested in quantum technologies, quantum constraint satisfaction problems, relationships and analogies between quantum computation and counting complexity, and analogies between quantum information and classical information in general. My background is primarily in computer science and combinatorics, but I also have a degree in physics, and consider it important to consider clear relationships between ideas in quantum information theory on the one hand, and foundational or conventional physics on the other.
Biography
I have simply collected the following links and abstracts from the arXiv. If you want further bibliographic information (e.g., because you are curious which of them have been published in peerreviewed venues), you can use other resources, such as Google Scholar.
Pauli Fusion: a computational model to realise quantum transformations from ZX terms
Authors: Niel de Beaudrap, Ross Duncan, Dominic Horsman, Simon Perdrix
Abstract: 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 nondeterministic heralded effects, similarly to measurementbased quantum computation. We describe sufficient conditions for Pauli Fusion procedures to be deterministically realisable, so that it performs a given transformation independently of its nondeterministic outcomes. This provides an operational model to realise ZX terms beyond the circuit model.
arXiv:1904.12817
On efficiently solvable cases of Quantum kSAT
Authors: Marco Aldi, Niel de Beaudrap, Sevag Gharibian, Seyran Saeedi
Abstract: The constraint satisfaction problems kSAT and Quantum kSAT (kQSAT) are canonical NPcomplete and QMA_1complete problems (for k>=3), respectively, where QMA_1 is a quantum generalization of NP with onesided error. Whereas kSAT has been wellstudied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for kQSAT. Here, we study the open problem of computing satisfying assignments to kQSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomialtime classical algorithm for kQSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for kQSAT instances from a certain nontrivial class, which allows us to obtain exponential speedups over brute force methods in some cases. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blowups from algebraic geometry.
arXiv:1712.09617
An integrity measure to benchmark quantum error correcting memories
Authors: Xiaosi Xu, Niel de Beaudrap, Joe O'Gorman, Simon C. Benjamin
Abstract: Rapidly developing experiments across multiple platforms now aim to realise small quantum codes, and so demonstrate a memory within which a logical qubit can be protected from noise. There is a need to benchmark the achievements in these diverse systems, and to compare the inherent power of the codes they rely upon. We describe a recentlyintroduced performance measure called integrity, which relates to the probability that an ideal agent will successfully 'guess' the state of a logical qubit after a period of storage in the memory. Integrity is straightforward to evaluate experimentally without state tomography and it can be related to various established metrics such as the logical fidelity and the pseudothreshold. We offer a set of experimental milestones that are steps towards demonstrating unconditionally superior encoded memories. Using intensive numerical simulations we compare memories based on the fivequbit code, the sevenqubit Steane code, and a ninequbit code which is the smallest instance of a surface code; we assess both the simple and faulttolerant implementations of each. While the 'best' code upon which to base a memory does vary according to the nature and severity of the noise, nevertheless certain trends emerge.
arXiv:1707.09951
The ZX calculus is a language for surface code lattice surgery
Authors: Niel de Beaudrap, Dominic Horsman
Abstract: A leading choice of error correction for scalable quantum computing is the surface code with lattice surgery. The basic lattice surgery operations, the merging and splitting of logical qubits, act nonunitarily on the logical states and are not easily captured by standard circuit notation. This raises the question of how best to design, verify, and optimise protocols that use lattice surgery, in particular in architectures with complex resource management issues. In this paper we demonstrate that the operations of the ZX calculus  a form of quantum diagrammatic reasoning based on bialgebras  match exactly the operations of lattice surgery. Red and green "spider" nodes match rough and smooth merges and splits, and follow the axioms of a dagger special associative Frobenius algebra. Some lattice surgery operations require nontrivial correction operations, which are captured natively in the use of the ZX calculus in the form of ensembles of diagrams. We give a first taste of the power of the calculus as a language for lattice surgery by considering two operations (T gates and producing a CNOT ) and show how ZX diagram rewrite rules give lattice surgery procedures for these operations that are novel, efficient, and highly configurable.
arXiv:1704.08670
The computational landscape of general physical theories
Authors: Jonathan Barrett, Niel de Beaudrap, Matty J. Hoban, Ciarán M. Lee
Abstract: There is good evidence that quantum computers are more powerful than classical computers, and that various simple modifications of quantum theory yield computational power that is dramatically greater still. However, these modifications also violate fundamental physical principles. This raises the question of whether there exists a physical theory, allowing computation more powerful than quantum, but which still respects those fundamental physical principles. Prior work by two of us introduced this question within a suitable framework for theories that make good operational sense, and showed that in any theory satisfying tomographic locality, the class of problems that can be solved efficiently is contained in the complexity class AWPP. Here, we show that this bound is tight, in the sense that there exists a theory, satisfying tomographic locality, as well as a basic principle of causality, which can efficiently decide everything in AWPP. Hence this theory can efficiently simulate any computation in this framework, including quantum computation.
arXiv:1702.08483
Minimally complex ion traps as modules for quantum communication and computing
Authors: Ramil Nigmatullin, Christopher J. Ballance, Niel de Beaudrap, Simon C. Benjamin
Abstract: Optically linked ion traps are promising as components of networkbased quantum technologies, including communication systems and modular computers. Experimental results achieved to date indicate that the fidelity of operations within each ion trap module will be far higher than the fidelity of operations involving the links; fortunately internal storage and processing can effectively upgrade the links through the process of purification. Here we perform the most detailed analysis to date on this purification task, using a protocol which is balanced to maximise fidelity while minimising the device complexity and the time cost of the process. Moreover we 'compile down' the quantum circuit to devicelevel operations including cooling and shutting events. We find that a linear trap with only five ions (two of one species, three of another) can support our protocol while incorporating desirable features such as 'global control', i.e. laser control pulses need only target an entire zone rather than differentiating one ion from its neighbour. To evaluate the capabilities of such a module we consider its use both as a universal communications node for quantum key distribution, and as the basic repeating unit of a quantum computer. For the latter case we evaluate the threshold for fault tolerant quantum computing using the surface code, finding acceptable fidelities for the 'raw' entangling link as low as 83% (or under 75% if an additional ion is available).
arXiv:1605.00111
On exact counting and quasiquantum complexity
Authors: Niel de Beaudrap
Abstract: We present characterisations of "exact" gapdefinable classes, in terms of indeterministic models of computation which slightly modify the standard model of quantum computation. This follows on work of Aaronson [arXiv:quantph/0412187], who shows that the counting class PP can be characterised in terms of boundederror "quantum" algorithms which use invertible (and possibly nonunitary) transformations, or postselections on events of nonzero probability. Our work considers similar modifications of the quantum computational model, but in the setting of exact algorithms, and algorithms with zero error and constant success probability. We show that the gapdefinable counting classes [J. Comput. Syst. Sci. 48 (1994), p.116] which bound exact and zeroerror quantum algorithms can be characterised in terms of "quantumlike" algorithms involving nonunitary gates, and that postselection and nonunitarity have equivalent power for exact quantum computation only if these classes collapse.
arXiv:1509.07789
A linear time algorithm for quantum 2SAT
Authors: Niel de Beaudrap, Sevag Gharibian
Abstract: The Boolean constraint satisfaction problem 3SAT is arguably the canonical NPcomplete problem. In contrast, 2SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of kSAT to the quantum setting, defining the problem "quantum kSAT". He showed that quantum 2SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unitcost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2SAT, and bears similarities with both the linear time 2SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].
arXiv:1508.07338
On computation with 'probabilities' modulo k
Authors: Niel de Beaudrap
Abstract: We propose a framework to study models of computation of indeterministic data, represented by abstract "distributions". In these distributions, probabilities are replaced by "amplitudes" drawn from a fixed semiring S, of which
the nonnegative reals, the complex numbers, finite fields GF(p^{r}), and cyclic rings Z_{k} are examples. Varying S yields different models of computation, which we may investigate to better understand the (likely) difference in power between randomised and quantum computation. The "modal quantum states" of Schumacher and Westmoreland [arXiv:1010.2929] are examples of such distributions, for S a finite field. For S = GF(2), Willcock and Sabry [arXiv:1102.3587] show that UNIQUESAT is solvable by polynomialtime uniform circuit families consisting of invertible gates. We characterize the decision problems solvable by polynomial uniform circuit families, using either invertible or "unitary" transformations over cyclic rings S = Z_{k}, or (in the case that k is a prime power) finite fields S = GF(k). In particular, for k a prime power, these are precisely the problems in the class Mod_{k}P.
arXiv:1405.7381
Quantum linear network coding as oneway quantum computation
Authors: Niel de Beaudrap, Martin Roetteler
Abstract: Network coding is a technique to maximize communication rates within a network, in communication protocols for simultaneous multiparty transmission of information. Linear network codes are examples of such protocols in which the local computations performed at the nodes in the network are limited to linear transformations of their input data (represented as elements of a ring, such as the integers modulo 2). The quantum linear network coding protocols of Kobayashi et al [arXiv:0908.1457 and arXiv:1012.4583] coherently simulate classical linear network codes, using supplemental classical communication. We demonstrate that these protocols correspond in a natural way to measurementbased quantum computations with graph states over over qudits [arXiv:quantph/0301052, arXiv:quantph/0603226, and arXiv:0704.1263] having a structure directly related to the network.
arXiv:1403.3533
Difficult instances of the counting problem for 2quantumSAT are very atypical
Authors: Niel de Beaudrap
Abstract: The problem 2quantumsatisfiability (2QSAT) is the generalisation of the 2CNFSAT problem to quantum bits, and is equivalent to determining whether or not a spin1/2 Hamiltonian with twobody terms is frustrationfree. Similarly to the classical problem 2SAT, the counting problem #2QSAT of determining the size (i.e. the dimension) of the set of satisfying states is #Pcomplete. However, if we consider random instances of #2QSAT in which constraints are sampled from the Haar measure, intractible instances have measure zero. An apparent reason for this is that almost all twoqubit constraints are entangled, which more readily give rise to longrange constraints. We investigate under which conditions product constraints also give rise to efficiently solvable families of #2QSAT instances. We consider #2QSAT involving only discrete distributions over tensor product operators, which interpolates between classical #2SAT and #2QSAT involving arbitrary product constraints. We find that such instances of #2QSAT, defined on ErdosRenyi graphs or bondpercolated lattices, are asymptotically almost surely efficiently solvable except to the extent that they are biased to resemble monotone instances of #2SAT.
arXiv:1403.1588
Interpreting the von Neumann entropy of graph Laplacians, and coentropic graphs
Authors: Niel de Beaudrap, Vittorio Giovannetti, Simone Severini, Richard Wilson
Abstract: For any graph, we define a rank1 operator on a bipartite tensor product space, with components associated to the set of vertices and edges respectively. We show that the partial traces of the operator are the Laplacian and the edgeLaplacian. This provides an interpretation of the von Neumann entropy of the (normalized) Laplacian as the amount of quantum entanglement between two systems corresponding to vertices and edges. In this framework, cospectral graphs correspond exactly to local unitarily equivalent pure states. Finally, we introduce the notion of coentropic graphs, that is, graphs with equal von Neumann entropy. The smallest coentropic (but not cospectral) graphs that we are able to construct have 8 vertices. The number of equivalence classes of coentropic graphs with n vertices and m edges is a lower bound to the number of (pure) bipartite entanglement classes with subsystems of corresponding dimension.
arXiv:1304.7946
On the complexity of solving linear congruences and computing nullspaces modulo a constant
Authors: Niel de Beaudrap
Abstract: We consider the problems of determining the feasibility of a linear congruence, producing a solution to a linear congruence, and finding a spanning set for the nullspace of an integer matrix, where each problem is considered modulo an arbitrary constant k>1. These problems are known to be complete for the logspace modular counting classes Mod_{k}L = coMod_{k}L in the special case that k is prime (Buntrock et al, 1992). By considering variants of standard logspace function classes  related to #L and functions computable by UL machines, but which only characterize the number of accepting paths modulo k  we show that these problems of linear algebra are also complete for coMod_{k}L for any constant k>1. Our results are obtained by defining a class of functions FUL_{k} which are low for Mod_{k}L and coMod_{k}L for k>1, using ideas similar to those used in the case of k prime in (Buntrock et al, 1992) to show closure of Mod_{k}L under NC^{1} reductions (including Mod_{k}L oracle reductions). In addition to the results above, we briefly consider the relationship of the class FUL_{k} for arbitrary moduli k to the class F.coMod_{k}L of functions whose output symbols are verifiable by coMod_{k}L algorithms; and consider what consequences such a comparison may have for oracle closure results of the form Mod_{k}L^Mod_{k}L = Mod_{k}L for composite k.
arXiv:1202.3949
A linearized stabilizer formalism for systems of finite dimension
Authors: Niel de Beaudrap
Abstract: The stabilizer formalism is a scheme, generalizing wellknown techniques developed by Gottesman [quantph/9705052] in the case of qubits, to efficiently simulate a class of transformations ("stabilizer circuits", which include the quantum Fourier transform and highly entangling operations) on standard basis states of ddimensional qudits. To determine the state of a simulated system, existing treatments involve the computation of cumulative phase factors which involve quadratic dependencies. We present a simple formalism in which Pauli operators are represented using displacement operators in discrete phase space, expressing the evolution of the state via linear transformations modulo D <= 2d. We thus obtain a simple proof that simulating stabilizer circuits on n qudits, involving any constant number of measurement rounds, is complete for the complexity class coMod_{d}L and may be simulated by O(log(n)^{2})depth boolean circuits for any constant d >= 2.
arXiv:1102.3354
Ground states of unfrustrated spin Hamiltonians satisfy an area law
Authors: Niel de Beaudrap, Tobias J. Osborne, Jens Eisert
Abstract: We show that ground states of unfrustrated quantum spin1/2 systems on general lattices satisfy an entanglement area law, provided that the Hamiltonian can be decomposed into nearestneighbor interaction terms which have entangled excited states. The ground state manifold can be efficiently described as the image of a lowdimensional subspace of low Schmidt measure, under an efficiently contractible treetensor network. This structure gives rise to the possibility of efficiently simulating the complete ground space (which is in general degenerate). We briefly discuss "nongeneric" cases, including highly degenerate interactions with product eigenbases, using a relationship to percolation theory. We finally assess the possibility of using such tree tensor networks to simulate almost frustrationfree spin models.
arXiv:1009.3051
Solving frustrationfree spin systems
Authors: N. de Beaudrap, M. Ohliger, T. J. Osborne, J. Eisert
Abstract: We identify a large class of quantum manybody systems that can be solved exactly: natural frustrationfree spin1/2 nearestneighbor Hamiltonians on arbitrary lattices. We show that the entire ground state manifold of such models can be found exactly by a tensor network of isometries acting on a space locally isomorphic to the symmetric subspace. Thus, for this wide class of models realspace renormalization can be made exact. Our findings also imply that every such frustrationfree spin model satisfies an area law for the entanglement entropy of the ground state, establishing a novel large class of models for which an area law is known. Finally, we show that our approach gives rise to an ansatz class useful for the simulation of almost frustrationfree models in a simple fashion, outperforming mean field theory.
arXiv:1005.3781
On restricted unitary Cayley graphs and symplectic transformations modulo n
Authors: Niel de Beaudrap
Abstract: We present some observations on a restricted variant of unitary Cayley graphs modulo n, and the implications for a decomposition of elements of symplectic operators over the integers modulo n. We define quadratic unitary Cayley graphs G_{n}, whose vertex set is the ring Z_{n}, and where residues a, b modulo n are adjacent if and only if their difference is a quadratic residue. By bounding the diameter of such graphs, we show an upper bound on the number of elementary operations (symplectic scalar multiplications, symplectic row swaps, and row additions or subtractions) required to decompose a symplectic matrix over Z_{n}. We also characterize the conditions on n for G_{n} to be a perfect graph.
arXiv:1002.0713
Unitarycircuit semantics for measurementbased computations
Authors: Niel de Beaudrap
Abstract: Oneway measurement based quantum computations (1WQC) may describe unitary transformations, via a composition of CPTP maps which are not all unitary themselves. This motivates the following decision problems: Is it possible to determine whether a “quantumtoquantum'' 1WQC procedure (having nontrivial input and output subsystems) performs a unitary transformation? Is it possible to describe precisely how such computations transform quantum states, by translation to a quantum circuit of comparable complexity? In this article, we present an efficient algorithm for transforming certain families of measurementbased computations into a reasonable unitary circuit model, in particular without employing the principle of deferred measurement.
arXiv:0906.4261
Quadratic Form Expansions for Unitaries
Authors: Niel de Beaudrap, Vincent Danos, Elham Kashefi, Martin Roetteler
Abstract: We introduce techniques to analyze unitary operations in terms of quadratic form expansions, a form similar to a sum over paths in the computational basis when the phase contributed by each path is described by a quadratic form over R. We show how to relate such a form to an entangled resource akin to that of the oneway measurement model of quantum computing. Using this, we describe various conditions under which it is possible to efficiently implement a unitary operation U, either when provided a quadratic form expansion for U as input, or by finding a quadratic form expansion for U from other input data.
arXiv:0801.2461
An extremal result for geometries in the oneway measurement model
Authors: Niel de Beaudrap, Martin Pei
Abstract: We present an extremal result for the class of graphs G which (together with some specified sets of input and output vertices, I and O) have a certain "flow" property introduced by Danos and Kashefi for the oneway measurement model of quantum computation. The existence of a flow for a triple (G,I,O) allows a unitary embedding to be derived from any choice of measurement bases allowed in the oneway measurement model. We prove an upper bound on the number of edges that a graph G may have, in order for a triple (G,I,O) to have a flow for some I, O ⊆ V(G), in terms of the number of vertices in G and O. This implies that finding a flow for a triple (G,I,O) when I = O = k (corresponding to unitary transformations in the measurement model) and V(G) = n can be performed in time O(k^{2}n), improving the earlier known bound of O(km) given in [quantph/0611284], where m = E(G).
arXiv:quantph/0702229
Finding flows in the oneway measurement model
Authors: Niel de Beaudrap
Abstract: The oneway measurement model is a framework for universal quantum computation, in which algorithms are partially described by a graph G of entanglement relations on a collection of qubits. A sufficient condition for an algorithm to perform a unitary embedding between two Hilbert spaces is for the graph G, together with input/output vertices I, O ⊆ V(G), to have a flow in the sense introduced by Danos and Kashefi [quantph/0506062]. For the special case of I = O = k, using a graphtheoretic characterization, I show that such flows are unique when they exist. This leads to an efficient algorithm for finding flows, by a reduction to solved problems in graph theory.
arXiv:quantph/0611284
Phase map decompositions for unitaries
Authors: Niel de Beaudrap, Vincent Danos, Elham Kashefi
Abstract: We propose a universal decomposition of unitary maps over a tensorial power of C^2, introducing the key concept of "phase maps", and investigate how this decomposition can be used to implement unitary maps directly in the measurementbased model for quantum computing. Specifically, we show how to extract from such a decomposition a matching entangled graph state (with inputs), and a set of measurements angles, when there is one. Next, we check whether the obtained graph state verifies a "flow" condition, which guarantees an execution order such that the dependent measurements and corrections of the pattern yield deterministic results. Using a graph theoretic characterization of flows, we can determine whether a flow can be constructed for a graph state in polynomial time. This approach yields an algorithmic procedure which, when it succeeds, may produce an efficient pattern for a given unitary.
arXiv:quantph/0603266
Onequbit fingerprinting schemes
Authors: J. Niel de Beaudrap
Abstract: Fingerprinting is a technique in communication complexity in which two parties (Alice and Bob) with large data sets send short messages to a third party (a referee), who attempts to compute some function of the larger data sets. For the equality function, the referee attempts to determine whether Alice's data and Bob's data are the same. In this paper, we consider the extreme scenario of performing fingerprinting where Alice and Bob both send either one bit (classically) or one qubit (in the quantum regime) messages to the referee for the equality problem. Restrictive bounds are demonstrated for the error probability of onebit fingerprinting schemes, and show that it is easy to construct onequbit fingerprinting schemes which can outperform any onebit fingerprinting scheme. The author hopes that this analysis will provide results useful for performing physical experiments, which may help to advance implementations for more general quantum communication protocols.
arXiv:quantph/0309036
Sharp Quantum vs. Classical Query Complexity Separations
Authors: J. Niel de Beaudrap, Richard Cleve, John Watrous
Abstract: We obtain the strongest separation between quantum and classical query complexity known to date  specifically, we define a blackbox problem that requires exponentially many queries in the classical boundederror case, but can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations). The problem is simple to define and the quantum algorithm solving it is also simple when described in terms of certain quantum Fourier transforms (QFTs) that have natural properties with respect to the algebraic structures of finite fields. These QFTs may be of independent interest, and we also investigate generalizations of them to noncommutative finite rings.
arXiv:quantph/0011065
Selected Publications

Tensor Network Rewriting Strategies for Satisfiability and Counting
Niel de Beaudrap‚ Aleks Kissinger and Konstantinos Meichanetzidis
2020.
Details about Tensor Network Rewriting Strategies for Satisfiability and Counting  BibTeX data for Tensor Network Rewriting Strategies for Satisfiability and Counting  Link to Tensor Network Rewriting Strategies for Satisfiability and Counting