Skip to main content

Niel de Beaudrap

Personal photo - Niel de Beaudrap

Niel de Beaudrap

Leaving date: 20th September 2020


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.


I was a postdoctoral research assistant in Oxford, and acting Work Package Leader, on the NQIT Project. I was also an organiser of the OASIS seminar series, and some-time organiser of the Quantum Group Worskhop. I left to take a lectureship in the Department of Informatics at the University of Sussex.

Here is a selection of my publications, up to the point that I left Oxford. 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 peer-reviewed venues), you can use other resources, such as Google Scholar.

Well-tempered ZX and ZH calculi
Authors: Niel de Beaudrap
Abstract: The ZX calculus is a mathematical tool to represent and analyse quantum operations by manipulating diagrams which in effect represent tensor networks. Two families of nodes of these networks are ones which commute with either Z rotations or X rotations, usually called "green nodes" and "red nodes" respectively. The original formulation of the ZX calculus was motivated in part by properties of the algebras formed by the green and red nodes: notably, that they form a bialgebra -- but only up to scalar factors. As a consequence, the diagram transformations and notation for certain unitary operations involve "scalar gadgets" which denote contributions to a normalising factor. We present renormalised generators for the ZX calculus, which form a bialgebra precisely. As a result, no scalar gadgets are required to represent the most common unitary transformations, and the corresponding diagram transformations are generally simpler. We also present a similar renormalised version of the ZH calculus. We obtain these results by an analysis of conditions under which various "idealised" rewrites are sound, leveraging the existing presentations of the ZX and ZH calculi.

Tensor Network Rewriting Strategies for Satisfiability and Counting
Authors: Niel de BeaudrapAleks Kissinger, Konstantinos Meichanetzidis
Abstract: We provide a graphical treatment of SAT and #SAT on equal footing. Instances of #SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over C in terms of diagrams built from simple generators, in which computation may be carried out by transformations of diagrams alone. In general, nodes of ZH diagrams take parameters over C which determine the tensor coefficients; for the standard representation of #SAT instances, the coefficients take the value 0 or 1. Then, by choosing the coefficients of a diagram to range over the boolean semiring B, we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the decision or counting version of the problem. We find that for classes known to be in P, such as 2-SAT and #XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as 3-SAT, or #P-complete, such as #2-SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and #CSPs and shows promise in aiding tensor network contraction-based algorithms.

Fast and effective techniques for T-count reduction via spider nest identities
Authors: Niel de Beaudrap, Xiaoning Bian, Quanlong Wang
Abstract: In fault-tolerant quantum computing systems, realising (approximately) universal quantum computation is usually described in terms of realising Clifford+T operations, which is to say a circuit of CNOT, Hadamard, and π/2-phase rotations, together with T operations (π/4-phase rotations). For many error correcting codes, fault-tolerant realisations of Clifford operations are significantly less resource-intensive than those of T gates, which motivates finding ways to realise the same transformation involving T-count (the number of T gates involved) which is as low as possible. Investigations into this problem [arXiv:1206.0758, 1303.2042, 1308.4134, 1601.07363, 1606.01904, 1701.00140] has led to observations that this problem is closely related to NP-hard tensor decomposition problems [arXiv:1712.01557] and is tantamount to the difficult problem of decoding exponentially long Reed-Muller codes [arXiv:1601.07363]. This problem then presents itself as one for which must be content in practise with approximate optimisation, in which one develops an array of tactics to be deployed through some pragmatic strategy. In this vein, we describe techniques to reduce the T-count, based on the effective application of "spider nest identities": easily recognised products of parity-phase operations which are equivalent to the identity operation. We demonstrate the effectiveness of such techniques by obtaining improvements in the T-counts of a number of circuits, in run-times which are typically less than the time required to make a fresh cup of coffee.

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 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.

On efficiently solvable cases of Quantum k-SAT
Authors: Marco Aldi, Niel de Beaudrap, Sevag Gharibian, Seyran Saeedi
Abstract: The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k>=3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT 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 polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial 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 3-QSAT 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 blow-ups from algebraic geometry.

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 recently-introduced 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 pseudo-threshold. 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 five-qubit code, the seven-qubit Steane code, and a nine-qubit code which is the smallest instance of a surface code; we assess both the simple and fault-tolerant 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.

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 non-unitarily 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 non-trivial 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 re-write rules give lattice surgery procedures for these operations that are novel, efficient, and highly configurable.

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.

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 network-based 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 device-level 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).

On exact counting and quasi-quantum complexity
Authors: Niel de Beaudrap
Abstract: We present characterisations of "exact" gap-definable classes, in terms of indeterministic models of computation which slightly modify the standard model of quantum computation. This follows on work of Aaronson [arXiv:quant-ph/0412187], who shows that the counting class PP can be characterised in terms of bounded-error "quantum" algorithms which use invertible (and possibly non-unitary) transformations, or postselections on events of non-zero 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 gap-definable counting classes [J. Comput. Syst. Sci. 48 (1994), p.116] which bound exact and zero-error quantum algorithms can be characterised in terms of "quantum-like" algorithms involving nonunitary gates, and that postselection and nonunitarity have equivalent power for exact quantum computation only if these classes collapse.

A linear time algorithm for quantum 2-SAT
Authors: Niel de Beaudrap, Sevag Gharibian
Abstract: The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT 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 2-SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].

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 semi-ring S, of which
the non-negative reals, the complex numbers, finite fields GF(p
r), and cyclic rings Zk 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 UNIQUE-SAT is solvable by polynomial-time 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 = Zk, 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 ModkP.

Quantum linear network coding as one-way 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 multi-party 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 measurement-based quantum computations with graph states over over qudits [arXiv:quant-ph/0301052, arXiv:quant-ph/0603226, and arXiv:0704.1263] having a structure directly related to the network.

Difficult instances of the counting problem for 2-quantum-SAT are very atypical
Authors: Niel de Beaudrap
Abstract: The problem 2-quantum-satisfiability (2-QSAT) is the generalisation of the 2-CNF-SAT problem to quantum bits, and is equivalent to determining whether or not a spin-1/2 Hamiltonian with two-body terms is frustration-free. Similarly to the classical problem 2-SAT, the counting problem #2-QSAT of determining the size (i.e. the dimension) of the set of satisfying states is #P-complete. However, if we consider random instances of #2-QSAT in which constraints are sampled from the Haar measure, intractible instances have measure zero. An apparent reason for this is that almost all two-qubit constraints are entangled, which more readily give rise to long-range constraints. We investigate under which conditions product constraints also give rise to efficiently solvable families of #2-QSAT instances. We consider #2-QSAT involving only discrete distributions over tensor product operators, which interpolates between classical #2-SAT and #2-QSAT involving arbitrary product constraints. We find that such instances of #2-QSAT, defined on Erdos--Renyi graphs or bond-percolated lattices, are asymptotically almost surely efficiently solvable except to the extent that they are biased to resemble monotone instances of #2-SAT.

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 rank-1 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 edge-Laplacian. 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.

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 ModkL = coModkL 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 coModkL for any constant k>1. Our results are obtained by defining a class of functions FULk which are low for ModkL and coModkL for k>1, using ideas similar to those used in the case of k prime in (Buntrock et al, 1992) to show closure of ModkL under NC1 reductions (including ModkL oracle reductions). In addition to the results above, we briefly consider the relationship of the class FULk for arbitrary moduli k to the class F.coModkL of functions whose output symbols are verifiable by coModkL algorithms; and consider what consequences such a comparison may have for oracle closure results of the form ModkL^ModkL = ModkL for composite k.

A linearized stabilizer formalism for systems of finite dimension
Authors: Niel de Beaudrap
Abstract: The stabilizer formalism is a scheme, generalizing well-known techniques developed by Gottesman [quant-ph/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 d-dimensional 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 coModdL and may be simulated by O(log(n)2)-depth boolean circuits for any constant d >= 2.

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 spin-1/2 systems on general lattices satisfy an entanglement area law, provided that the Hamiltonian can be decomposed into nearest-neighbor interaction terms which have entangled excited states. The ground state manifold can be efficiently described as the image of a low-dimensional subspace of low Schmidt measure, under an efficiently contractible tree-tensor network. This structure gives rise to the possibility of efficiently simulating the complete ground space (which is in general degenerate). We briefly discuss "non-generic" 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 frustration-free spin models.

Solving frustration-free spin systems
Authors: N. de Beaudrap, M. Ohliger, T. J. Osborne, J. Eisert
Abstract: We identify a large class of quantum many-body systems that can be solved exactly: natural frustration-free spin-1/2 nearest-neighbor 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 real-space renormalization can be made exact. Our findings also imply that every such frustration-free 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 frustration-free models in a simple fashion, outperforming mean field theory.

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 Gn, whose vertex set is the ring Zn, 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 Zn. We also characterize the conditions on n for Gn to be a perfect graph.

Unitary-circuit semantics for measurement-based computations 
Authors: Niel de Beaudrap
Abstract: One-way 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 “quantum-to-quantum'' 1WQC procedure (having non-trivial 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 measurement-based computations into a reasonable unitary circuit model, in particular without employing the principle of deferred measurement.

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 one-way 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.

An extremal result for geometries in the one-way 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 one-way 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 one-way 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(k2n), improving the earlier known bound of O(km) given in [quant-ph/0611284], where m = |E(G)|.

Finding flows in the one-way measurement model
Authors: Niel de Beaudrap
Abstract: The one-way 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 [quant-ph/0506062]. For the special case of |I| = |O| = k, using a graph-theoretic 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.

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 measurement-based 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.

One-qubit 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 one-bit fingerprinting schemes, and show that it is easy to construct one-qubit fingerprinting schemes which can outperform any one-bit 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.

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 black-box problem that requires exponentially many queries in the classical bounded-error 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.