Search Results

Documents authored by de Beaudrap, Niel

Document
DOI: 10.4230/LIPIcs.MFCS.2024.20
Simple Qudit ZX and ZH Calculi, via Integrals

Authors: Niel de Beaudrap and Richard D. P. East

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
The ZX calculus and ZH calculus use diagrams to denote and compute properties of quantum operations, using "rewrite rules" to transform between diagrams which denote the same operator through a functorial semantic map. Different semantic maps give rise to different rewrite systems, which may prove more convenient for different purposes. Using discrete measures, we describe semantic maps for ZX and ZH diagrams, well-suited to analyse unitary circuits and measurements on qudits of any fixed dimension D > 1 as a single "ZXH-calculus". We demonstrate rewrite rules for the "stabiliser fragment" of the ZX calculus and a "multicharacter fragment" of the ZH calculus.
Cite as

Niel de Beaudrap and Richard D. P. East. Simple Qudit ZX and ZH Calculi, via Integrals. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{debeaudrap_et_al:LIPIcs.MFCS.2024.20,
  author =	{de Beaudrap, Niel and East, Richard D. P.},
  title =	{{Simple Qudit ZX and ZH Calculi, via Integrals}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.20},
  URN =		{urn:nbn:de:0030-drops-205761},
  doi =		{10.4230/LIPIcs.MFCS.2024.20},
  annote =	{Keywords: ZX-calculus, ZH-calculus, qudits, string diagrams, discrete integrals}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.119
Circuit Extraction for ZX-Diagrams Can Be #P-Hard

Authors: Niel de Beaudrap, Aleks Kissinger, and John van de Wetering

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
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 ≥ 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.
Cite as

Niel de Beaudrap, Aleks Kissinger, and John van de Wetering. Circuit Extraction for ZX-Diagrams Can Be #P-Hard. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 119:1-119:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{debeaudrap_et_al:LIPIcs.ICALP.2022.119,
  author =	{de Beaudrap, Niel and Kissinger, Aleks and van de Wetering, John},
  title =	{{Circuit Extraction for ZX-Diagrams Can Be #P-Hard}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{119:1--119:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.119},
  URN =		{urn:nbn:de:0030-drops-164601},
  doi =		{10.4230/LIPIcs.ICALP.2022.119},
  annote =	{Keywords: ZX-calculus, circuit extraction, quantum circuits, #P}
}
Document
DOI: 10.4230/LIPIcs.TQC.2020.11
Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities

Authors: Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

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 [Matthew Amy et al., 2013; Gosset et al., 2014; Matthew Amy et al., 2014; Matthew Amy et al., 2018; Earl T. Campbell and Mark Howard, 2017; Matthew Amy and Michele Mosca, 2019] has led to observations that this problem is closely related to NP-hard tensor decomposition problems [Luke E. Heyfron and Earl T. Campbell, 2018] and is tantamount to the difficult problem of decoding exponentially long Reed-Muller codes [Matthew Amy and Michele Mosca, 2019]. 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.
Cite as

Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{debeaudrap_et_al:LIPIcs.TQC.2020.11,
  author =	{de Beaudrap, Niel and Bian, Xiaoning and Wang, Quanlong},
  title =	{{Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.11},
  URN =		{urn:nbn:de:0030-drops-120705},
  doi =		{10.4230/LIPIcs.TQC.2020.11},
  annote =	{Keywords: T-count, Parity-phase operations, Phase gadgets, Clifford hierarchy, ZX calculus}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.38
On Efficiently Solvable Cases of Quantum k-SAT

Authors: Marco Aldi, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

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 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; we hope these prove useful elsewhere.
Cite as

Marco Aldi, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi. On Efficiently Solvable Cases of Quantum k-SAT. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aldi_et_al:LIPIcs.MFCS.2018.38,
  author =	{Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran},
  title =	{{On Efficiently Solvable Cases of Quantum k-SAT}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.38},
  URN =		{urn:nbn:de:0030-drops-96201},
  doi =		{10.4230/LIPIcs.MFCS.2018.38},
  annote =	{Keywords: search complexity, local Hamiltonian, Quantum SAT, algebraic geometry}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.27
A Linear Time Algorithm for Quantum 2-SAT

Authors: Niel de Beaudrap and Sevag Gharibian

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

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

Niel de Beaudrap and Sevag Gharibian. A Linear Time Algorithm for Quantum 2-SAT. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{debeaudrap_et_al:LIPIcs.CCC.2016.27,
  author =	{de Beaudrap, Niel and Gharibian, Sevag},
  title =	{{A Linear Time Algorithm for Quantum 2-SAT}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.27},
  URN =		{urn:nbn:de:0030-drops-58363},
  doi =		{10.4230/LIPIcs.CCC.2016.27},
  annote =	{Keywords: quantum 2-SAT, transfer matrix, strongly connected components, limited backtracking, local Hamiltonian}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.118
Difficult Instances of the Counting Problem for 2-quantum-SAT are Very Atypical

Authors: Niel de Beaudrap

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
The problem 2-QUANTUM-SATISFIABILITY (QSAT[2]) 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. imilarly to the classical problem #SAT[2], the counting problem #QSAT[2] of determining the size (i.e. the dimension) of the set of satisfying states is #P-complete. However, if we consider random instances of QSAT[2] 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 #QSAT[2] instances. We consider #QSAT[2] involving only discrete distributions over tensor product operators, which interpolates between classical #SAT[2] and #QSAT[2] involving arbitrary product constraints. We find that such instances of #QSAT[2], defined on Erdös-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 #SAT[2].
Cite as

Niel de Beaudrap. Difficult Instances of the Counting Problem for 2-quantum-SAT are Very Atypical. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 118-140, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{debeaudrap:LIPIcs.TQC.2014.118,
  author =	{de Beaudrap, Niel},
  title =	{{Difficult Instances of the Counting Problem for 2-quantum-SAT are Very Atypical}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{118--140},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.118},
  URN =		{urn:nbn:de:0030-drops-48129},
  doi =		{10.4230/LIPIcs.TQC.2014.118},
  annote =	{Keywords: Frustration-free, Hamiltonian, quantum, counting, satisfiability}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.217
Quantum Linear Network Coding as One-way Quantum Computation

Authors: Niel de Beaudrap and Martin Roetteler

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

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. 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 qudits having a structure directly related to the network.
Cite as

Niel de Beaudrap and Martin Roetteler. Quantum Linear Network Coding as One-way Quantum Computation. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 217-233, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{debeaudrap_et_al:LIPIcs.TQC.2014.217,
  author =	{de Beaudrap, Niel and Roetteler, Martin},
  title =	{{Quantum Linear Network Coding as One-way Quantum Computation}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{217--233},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.217},
  URN =		{urn:nbn:de:0030-drops-48189},
  doi =		{10.4230/LIPIcs.TQC.2014.217},
  annote =	{Keywords: Network coding, quantum computing, measurement-based computation, simulation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact