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

Niel de Beaudrap

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

ResearcherUnclaimed source record
quant-phComputational Complexitymath.COcond-mat.str-elData Structures and AlgorithmsInformation TheoryLogic in Computer Sciencemath.ITmath.NT

Catalog footprint

What is connected

15works
9topics
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

15 published item(s)

preprint2022arXiv

Circuit Extraction for ZX-diagrams can be #P-hard

The ZX-calculus is a graphical language for reasoning about quantum computation using ZX-diagrams, a certain flexible generalisation of quantum circuits that can be used to represent linear maps from $m$ to $n$ qubits for any $m,n \geq 0$. Some applications for the ZX-calculus, such as quantum circuit optimisation and synthesis, rely on being able to efficiently translate a ZX-diagram back into a quantum circuit of comparable size. While several sufficient conditions are known for describing families of ZX-diagrams that can be efficiently transformed back into circuits, it has previously been conjectured that the general problem of circuit extraction is hard. That is, that it should not be possible to efficiently convert an arbitrary ZX-diagram describing a unitary linear map into an equivalent quantum circuit. In this paper we prove this conjecture by showing that the circuit extraction problem is #P-hard, and so is itself at least as hard as strong simulation of quantum circuits. In addition to our main hardness result, which relies specifically on the circuit representation, we give a representation-agnostic hardness result. Namely, we show that any oracle that takes as input a ZX-diagram description of a unitary and produces samples of the output of the associated quantum computation enables efficient probabilistic solutions to NP-complete problems.

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

Techniques to Reduce $π/4$-Parity-Phase Circuits, Motivated by the ZX Calculus

To approximate arbitrary unitary transformations on one or more qubits, one must perform transformations which are outside of the Clifford group. The gate most commonly considered for this purpose is the T = diag(1, exp(i π/4)) gate. As T gates are computationally expensive to perform fault-tolerantly in the most promising error-correction technologies, minimising the "T-count" (the number of T gates) required to realise a given unitary in a Clifford+T circuit is of great interest. We describe techniques to find circuits with reduced T-count in unitary circuits, which develop on the ideas of Heyfron and Campbell [arXiv:1712.01557] with the help of the ZX calculus. Following [arXiv:1712.01557], we reduce the problem to that of minimising the T count of a CNOT+T circuit. The ZX calculus motivates a further reduction to simplifying a product of commuting "π/4-parity-phase" operations: diagonal unitary transformations which induce a relative phase of exp(i π/4) depending on the outcome of a parity computation on the standard basis (which motivated Kissinger and van de Wetering [1903.10477] to introduce "phase gadgets"). For a number of standard benchmark circuits, we show that these techniques -- in some cases supplemented by the TODD subroutine of Heyfron and Campbell [arXiv:1712.01557] -- yield T-counts comparable to or better than the best previously known results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The ZX calculus is a language for surface code lattice surgery

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Minimally complex ion traps as modules for quantum communication and computing

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

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A linear time algorithm for quantum 2-SAT

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

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On exact counting and quasi-quantum complexity

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Quantum linear network coding as one-way quantum computation

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Difficult instances of the counting problem for 2-quantum-SAT are very atypical

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On computation with 'probabilities' modulo k

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 $\mathbb F_{p^r}$, and cyclic rings $\mathbb 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 = \mathbb F_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 = \mathbb Z_k$, or (in the case that $k$ is a prime power) finite fields $S = \mathbb F_k$. In particular, for $k$ a prime power, these are precisely the problems in the class $\mathsf{Mod}_k\mathsf P$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Interpreting the von Neumann entropy of graph Laplacians, and coentropic graphs

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the complexity of solving linear congruences and computing nullspaces modulo a constant

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

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Ground states of unfrustrated spin Hamiltonians satisfy an area law

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On restricted unitary Cayley graphs and symplectic transformations modulo n

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.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Quadratic Form Expansions for Unitaries

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 $\mathbb 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.

0 citations0 reviewsNo code linkedOpen access