18 Search Results for "van Dam, Wim"

Volume

LIPIcs, Volume 135

14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

TQC 2019, June 3-5, 2019, University of Maryland, College Park, Maryland, USA

Editors: Wim van Dam and Laura Mančinska

Document
Complete Volume
DOI: 10.4230/LIPIcs.TQC.2019
LIPIcs, Volume 135, TQC'19, Complete Volume

Authors: Wim van Dam and Laura Mančinska

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
LIPIcs, Volume 135, TQC'19, Complete Volume
Cite as

14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{vandam_et_al:LIPIcs.TQC.2019,
  title =	{{LIPIcs, Volume 135, TQC'19, Complete Volume}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019},
  URN =		{urn:nbn:de:0030-drops-105052},
  doi =		{10.4230/LIPIcs.TQC.2019},
  annote =	{Keywords: Theory of computation, Quantum computation theory, Quantum complexity theory, Quantum communication complexity}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TQC.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Wim van Dam and Laura Mančinska

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 0:i-0:xiii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vandam_et_al:LIPIcs.TQC.2019.0,
  author =	{van Dam, Wim and Man\v{c}inska, Laura},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{0:i--0:xiii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.0},
  URN =		{urn:nbn:de:0030-drops-103920},
  doi =		{10.4230/LIPIcs.TQC.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.1
On Quantum Chosen-Ciphertext Attacks and Learning with Errors

Authors: Gorjan Alagic, Stacey Jeffery, Maris Ozols, and Alexander Poremba

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
Quantum computing is a significant threat to classical public-key cryptography. In strong "quantum access" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key requires a linear number of decryption queries. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.
Cite as

Gorjan Alagic, Stacey Jeffery, Maris Ozols, and Alexander Poremba. On Quantum Chosen-Ciphertext Attacks and Learning with Errors. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{alagic_et_al:LIPIcs.TQC.2019.1,
  author =	{Alagic, Gorjan and Jeffery, Stacey and Ozols, Maris and Poremba, Alexander},
  title =	{{On Quantum Chosen-Ciphertext Attacks and Learning with Errors}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.1},
  URN =		{urn:nbn:de:0030-drops-103939},
  doi =		{10.4230/LIPIcs.TQC.2019.1},
  annote =	{Keywords: quantum chosen-ciphertext security, quantum attacks, learning with errors}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.2
Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge

Authors: Shalev Ben-David and Robin Kothari

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to |0> on a 0-input and a state close to |1> on a 1-input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0-input and 1-input are distinguishable. Using this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zero-error and bounded-error quantum query complexity of f respectively, improving on the previously known sixth power relationship. We also define a query measure based on quantum statistical zero-knowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity. Lastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zero-error quantum query complexity or for QSZK would imply a general lifting theorem for bounded-error quantum query complexity.
Cite as

Shalev Ben-David and Robin Kothari. Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.TQC.2019.2,
  author =	{Ben-David, Shalev and Kothari, Robin},
  title =	{{Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.2},
  URN =		{urn:nbn:de:0030-drops-103944},
  doi =		{10.4230/LIPIcs.TQC.2019.2},
  annote =	{Keywords: Quantum query complexity, quantum algorithms}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.3
Circuit Transformations for Quantum Architectures

Authors: Andrew M. Childs, Eddie Schoute, and Cem M. Unsal

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
Quantum computer architectures impose restrictions on qubit interactions. We propose efficient circuit transformations that modify a given quantum circuit to fit an architecture, allowing for any initial and final mapping of circuit qubits to architecture qubits. To achieve this, we first consider the qubit movement subproblem and use the ROUTING VIA MATCHINGS framework to prove tighter bounds on parallel routing. In practice, we only need to perform partial permutations, so we generalize ROUTING VIA MATCHINGS to that setting. We give new routing procedures for common architecture graphs and for the generalized hierarchical product of graphs, which produces subgraphs of the Cartesian product. Secondly, for serial routing, we consider the TOKEN SWAPPING framework and extend a 4-approximation algorithm for general graphs to support partial permutations. We apply these routing procedures to give several circuit transformations, using various heuristic qubit placement subroutines. We implement these transformations in software and compare their performance for large quantum circuits on grid and modular architectures, identifying strategies that work well in practice.
Cite as

Andrew M. Childs, Eddie Schoute, and Cem M. Unsal. Circuit Transformations for Quantum Architectures. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{childs_et_al:LIPIcs.TQC.2019.3,
  author =	{Childs, Andrew M. and Schoute, Eddie and Unsal, Cem M.},
  title =	{{Circuit Transformations for Quantum Architectures}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.3},
  URN =		{urn:nbn:de:0030-drops-103958},
  doi =		{10.4230/LIPIcs.TQC.2019.3},
  annote =	{Keywords: quantum circuit, quantum architectures, circuit mapping}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.4
The RGB No-Signalling Game

Authors: Xavier Coiteux-Roy and Claude Crépeau

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
Introducing the simplest of all No-Signalling Games: the RGB Game where two verifiers interrogate two provers, Alice and Bob, far enough from each other that communication between them is too slow to be possible. Each prover may be independently queried one of three possible colours: Red, Green or Blue. Let a be the colour announced to Alice and b be announced to Bob. To win the game they must reply colours x (resp. y) such that a != x != y != b. This work focuses on this new game mainly as a pedagogical tool for its simplicity but also because it triggered us to introduce a new set of definitions for reductions among multi-party probability distributions and related non-locality classes. We show that a particular winning strategy for the RGB Game is equivalent to the PR-Box of Popescu-Rohrlich and thus No-Signalling. Moreover, we use this example to define No-Signalling in a new useful way, as the intersection of two natural classes of multi-party probability distributions called one-way signalling. We exhibit a quantum strategy able to beat the classical local maximum winning probability of 8/9 shifting it up to 11/12. Optimality of this quantum strategy is demonstrated using the standard tool of semidefinite programming.
Cite as

Xavier Coiteux-Roy and Claude Crépeau. The RGB No-Signalling Game. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{coiteuxroy_et_al:LIPIcs.TQC.2019.4,
  author =	{Coiteux-Roy, Xavier and Cr\'{e}peau, Claude},
  title =	{{The RGB No-Signalling Game}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.4},
  URN =		{urn:nbn:de:0030-drops-103965},
  doi =		{10.4230/LIPIcs.TQC.2019.4},
  annote =	{Keywords: No-Signalling, Quantum Entanglement, Non-Locality, Bell inequality, Semidefinite Programming, Non-locality Hierarchy}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.5
On the Qubit Routing Problem

Authors: Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
We introduce a new architecture-agnostic methodology for mapping abstract quantum circuits to realistic quantum computing devices with restricted qubit connectivity, as implemented by Cambridge Quantum Computing’s t|ket> compiler. We present empirical results showing the effectiveness of this method in terms of reducing two-qubit gate depth and two-qubit gate count, compared to other implementations.
Cite as

Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the Qubit Routing Problem. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cowtan_et_al:LIPIcs.TQC.2019.5,
  author =	{Cowtan, Alexander and Dilkes, Silas and Duncan, Ross and Krajenbrink, Alexandre and Simmons, Will and Sivarajah, Seyon},
  title =	{{On the Qubit Routing Problem}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{5:1--5:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.5},
  URN =		{urn:nbn:de:0030-drops-103972},
  doi =		{10.4230/LIPIcs.TQC.2019.5},
  annote =	{Keywords: Quantum Computing, Qubit routing, Compilation}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.6
Applications of the Quantum Algorithm for st-Connectivity

Authors: Kai DeLorenzo, Shelby Kimmel, and R. Teal Witter

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
We present quantum algorithms for various problems related to graph connectivity. We give simple and query-optimal algorithms for cycle detection and odd-length cycle detection (bipartiteness) using a reduction to st-connectivity. Furthermore, we show that our algorithm for cycle detection has improved performance under the promise of large circuit rank or a small number of edges. We also provide algorithms for detecting even-length cycles and for estimating the circuit rank of a graph. All of our algorithms have logarithmic space complexity.
Cite as

Kai DeLorenzo, Shelby Kimmel, and R. Teal Witter. Applications of the Quantum Algorithm for st-Connectivity. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{delorenzo_et_al:LIPIcs.TQC.2019.6,
  author =	{DeLorenzo, Kai and Kimmel, Shelby and Witter, R. Teal},
  title =	{{Applications of the Quantum Algorithm for st-Connectivity}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.6},
  URN =		{urn:nbn:de:0030-drops-103984},
  doi =		{10.4230/LIPIcs.TQC.2019.6},
  annote =	{Keywords: graphs, algorithms, query complexity, quantum algorithms, span programs}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.7
Bayesian ACRONYM Tuning

Authors: John Gamble, Christopher Granade, and Nathan Wiebe

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
We provide an algorithm that uses Bayesian randomized benchmarking in concert with a local optimizer, such as SPSA, to find a set of controls that optimizes that average gate fidelity. We call this method Bayesian ACRONYM tuning as a reference to the analogous ACRONYM tuning algorithm. Bayesian ACRONYM distinguishes itself in its ability to retain prior information from experiments that use nearby control parameters; whereas traditional ACRONYM tuning does not use such information and can require many more measurements as a result. We prove that such information reuse is possible under the relatively weak assumption that the true model parameters are Lipschitz-continuous functions of the control parameters. We also perform numerical experiments that demonstrate that over-rotation errors in single qubit gates can be automatically tuned from 88% to 99.95% average gate fidelity using less than 1kB of data and fewer than 20 steps of the optimizer.
Cite as

John Gamble, Christopher Granade, and Nathan Wiebe. Bayesian ACRONYM Tuning. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gamble_et_al:LIPIcs.TQC.2019.7,
  author =	{Gamble, John and Granade, Christopher and Wiebe, Nathan},
  title =	{{Bayesian ACRONYM Tuning}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.7},
  URN =		{urn:nbn:de:0030-drops-103995},
  doi =		{10.4230/LIPIcs.TQC.2019.7},
  annote =	{Keywords: Quantum Computing, Randomized Benchmarking}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.8
A Compressed Classical Description of Quantum States

Authors: David Gosset and John Smolin

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an n-qubit state psi consists of its inner products with O(sqrt{2^n}) stabilizer states. A quantum state initially specified by its 2^n entries in the computational basis can be compressed to this form in time O(2^n poly(n)), and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an exponential improvement over Raz’s protocol in terms of computational efficiency.
Cite as

David Gosset and John Smolin. A Compressed Classical Description of Quantum States. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 8:1-8:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gosset_et_al:LIPIcs.TQC.2019.8,
  author =	{Gosset, David and Smolin, John},
  title =	{{A Compressed Classical Description of Quantum States}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{8:1--8:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.8},
  URN =		{urn:nbn:de:0030-drops-104005},
  doi =		{10.4230/LIPIcs.TQC.2019.8},
  annote =	{Keywords: Quantum computation, Quantum communication complexity, Classical simulation}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.9
Approximate Unitary n^{2/3}-Designs Give Rise to Quantum Channels with Super Additive Classical Holevo Capacity

Authors: Aditya Nema and Pranab Sen

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
In a breakthrough, Hastings [2009] showed that there exist quantum channels whose classical Holevo capacity is superadditive i.e. more classical information can be transmitted by quantum encoding strategies entangled across multiple channel uses as compared to unentangled quantum encoding strategies. Hastings' proof used Haar random unitaries to exhibit superadditivity. In this paper we show that a unitary chosen uniformly at random from an approximate n^{2/3}-design gives rise to a quantum channel with superadditive classical Holevo capacity, where n is the dimension of the unitary exhibiting the Stinespring dilation of the channel superoperator. We do so by showing that the minimum output von Neumann entropy of a quantum channel arising from an approximate unitary n^{2/3}-design is subadditive, which by Shor’s work [2002] implies superadditivity of classical Holevo capacity of quantum channels. We follow the geometric functional analytic approach of Aubrun, Szarek and Werner [Aubrun et al., 2010] in order to prove our result. More precisely we prove a sharp Dvoretzky-like theorem stating that, with high probability under the choice of a unitary from an approximate t-design, random subspaces of large dimension make a Lipschitz function take almost constant value. Such theorems were known earlier only for Haar random unitaries. We obtain our result by appealing to Low’s technique [2009] for proving concentration of measure for an approximate t-design, combined with a stratified analysis of the variational behaviour of Lipschitz functions on the unit sphere in high dimension. The stratified analysis is the main technical advance of this work. Haar random unitaries require at least Omega(n^2) random bits in order to describe them with good precision. In contrast, there exist exact n^{2/3}-designs using only O(n^{2/3} log n) random bits [Kuperberg, 2006]. Thus, our work can be viewed as a partial derandomisation of Hastings' result, and a step towards the quest of finding an explicit quantum channel with superadditive classical Holevo capacity.
Cite as

Aditya Nema and Pranab Sen. Approximate Unitary n^{2/3}-Designs Give Rise to Quantum Channels with Super Additive Classical Holevo Capacity. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nema_et_al:LIPIcs.TQC.2019.9,
  author =	{Nema, Aditya and Sen, Pranab},
  title =	{{Approximate Unitary n^\{2/3\}-Designs Give Rise to Quantum Channels with Super Additive Classical Holevo Capacity}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.9},
  URN =		{urn:nbn:de:0030-drops-104015},
  doi =		{10.4230/LIPIcs.TQC.2019.9},
  annote =	{Keywords: classical Holevo capacity, super additivity, Haar measure, approximate unitary t-design, polyomial approximation}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.10
Parameterization of Tensor Network Contraction

Authors: Bryan O'Gorman

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
We present a conceptually clear and algorithmically useful framework for parameterizing the costs of tensor network contraction. Our framework is completely general, applying to tensor networks with arbitrary bond dimensions, open legs, and hyperedges. The fundamental objects of our framework are rooted and unrooted contraction trees, which represent classes of contraction orders. Properties of a contraction tree correspond directly and precisely to the time and space costs of tensor network contraction. The properties of rooted contraction trees give the costs of parallelized contraction algorithms. We show how contraction trees relate to existing tree-like objects in the graph theory literature, bringing to bear a wide range of graph algorithms and tools to tensor network contraction. Independent of tensor networks, we show that the edge congestion of a graph is almost equal to the branchwidth of its line graph.
Cite as

Bryan O'Gorman. Parameterization of Tensor Network Contraction. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ogorman:LIPIcs.TQC.2019.10,
  author =	{O'Gorman, Bryan},
  title =	{{Parameterization of Tensor Network Contraction}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.10},
  URN =		{urn:nbn:de:0030-drops-104025},
  doi =		{10.4230/LIPIcs.TQC.2019.10},
  annote =	{Keywords: tensor networks, parameterized complexity, tree embedding, congestion}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.66
On Learning Linear Functions from Subset and Its Applications in Quantum Computing

Authors: Gábor Ivanyos, Anupam Prakash, and Miklos Santha

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gábor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.
Cite as

Gábor Ivanyos, Anupam Prakash, and Miklos Santha. On Learning Linear Functions from Subset and Its Applications in Quantum Computing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ivanyos_et_al:LIPIcs.ESA.2018.66,
  author =	{Ivanyos, G\'{a}bor and Prakash, Anupam and Santha, Miklos},
  title =	{{On Learning Linear Functions from Subset and Its Applications in Quantum Computing}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.66},
  URN =		{urn:nbn:de:0030-drops-95299},
  doi =		{10.4230/LIPIcs.ESA.2018.66},
  annote =	{Keywords: Learning from subset, hidden shift problem, quantum algorithms, linearization}
}
Document
DOI: 10.4230/LIPIcs.TQC.2018.7
Two-qubit Stabilizer Circuits with Recovery I: Existence

Authors: Wim van Dam and Raymond Wong

Published in: LIPIcs, Volume 111, 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)

Abstract
In this paper, we further investigate the many ways of using stabilizer operations to generate a single qubit output from a two-qubit state. In particular, by restricting the input to certain product states, we discover probabilistic operations capable of transforming stabilizer circuit outputs back into stabilizer circuit inputs. These secondary operations are ideally suited for recovery purposes and require only one extra resource input to proceed. As a result of reusing qubits in this manner, we present an alternative to the original state preparation process that can lower the overall costs of executing a two-qubit stabilizer procedure involving non-stabilizer resources.
Cite as

Wim van Dam and Raymond Wong. Two-qubit Stabilizer Circuits with Recovery I: Existence. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 111, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vandam_et_al:LIPIcs.TQC.2018.7,
  author =	{van Dam, Wim and Wong, Raymond},
  title =	{{Two-qubit Stabilizer Circuits with Recovery I: Existence}},
  booktitle =	{13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-080-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{111},
  editor =	{Jeffery, Stacey},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2018.7},
  URN =		{urn:nbn:de:0030-drops-92540},
  doi =		{10.4230/LIPIcs.TQC.2018.7},
  annote =	{Keywords: stabilizer circuit, recovery circuit, magic state}
}
  • Refine by Author
  • 6 van Dam, Wim
  • 2 Childs, Andrew M.
  • 2 Mančinska, Laura
  • 2 Wong, Raymond
  • 1 Alagic, Gorjan
  • Show More...

  • Refine by Classification
  • 8 Theory of computation → Quantum computation theory
  • 5 Theory of computation → Quantum information theory
  • 4 Theory of computation → Quantum complexity theory
  • 3 General and reference → General conference proceedings
  • 3 Hardware → Quantum computation
  • Show More...

  • Refine by Keyword
  • 4 quantum algorithms
  • 2 Quantum Computing
  • 2 magic state
  • 2 query complexity
  • 2 recovery circuit
  • Show More...

  • Refine by Type
  • 17 document
  • 1 volume

  • Refine by Publication Year
  • 13 2019
  • 3 2018
  • 1 2014
  • 1 2016

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