21 Search Results for "Beigi, Salman"

Volume

LIPIcs, Volume 44

10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

TQC 2015, May 20-22, 2015, Brussels, Belgium

Editors: Salman Beigi and Robert König

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.30
Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources

Authors: Salman Beigi, Andrej Bogdanov, Omid Etesami, and Siyao Guo

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
Let F be a finite alphabet and D be a finite set of distributions over F. A Generalized Santha-Vazirani (GSV) source of type (F, D), introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence (F_1, ..., F_n) in F^n, where F_i is a sample from some distribution d in D whose choice may depend on F_1, ..., F_{i-1}. We show that all GSV source types (F, D) fall into one of three categories: (1) non-extractable; (2) extractable with error n^{-Theta(1)}; (3) extractable with error 2^{-Omega(n)}. We provide essentially randomness-optimal extraction algorithms for extractable sources. Our algorithm for category (2) sources extracts one bit with error epsilon from n = poly(1/epsilon) samples in time linear in n. Our algorithm for category (3) sources extracts m bits with error epsilon from n = O(m + log 1/epsilon) samples in time min{O(m2^m * n),n^{O(|F|)}}. We also give algorithms for classifying a GSV source type (F, D): Membership in category (1) can be decided in NP, while membership in category (3) is polynomial-time decidable.
Cite as

Salman Beigi, Andrej Bogdanov, Omid Etesami, and Siyao Guo. Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{beigi_et_al:LIPIcs.APPROX-RANDOM.2018.30,
  author =	{Beigi, Salman and Bogdanov, Andrej and Etesami, Omid and Guo, Siyao},
  title =	{{Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.30},
  URN =		{urn:nbn:de:0030-drops-94349},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.30},
  annote =	{Keywords: feasibility of randomness extraction, extractor lower bounds, martingales}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.TQC.2015
LIPIcs, Volume 44, TQC'15, Complete Volume

Authors: Salman Beigi and Robert Koenig

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
LIPIcs, Volume 44, TQC'15, Complete Volume
Cite as

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

Copy BibTex To Clipboard

@Proceedings{beigi_et_al:LIPIcs.TQC.2015,
  title =	{{LIPIcs, Volume 44, TQC'15, Complete Volume}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015},
  URN =		{urn:nbn:de:0030-drops-55649},
  doi =		{10.4230/LIPIcs.TQC.2015},
  annote =	{Keywords: Data Encryption, E.4 Coding and Information Theory, F Theory of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TQC.2015.i
Front Matter, Table of Contents, Preface, Committees

Authors: Salman Beigi and Robert König

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
Front Matter, Table of Contents, Preface, Committees
Cite as

10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. i-xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{beigi_et_al:LIPIcs.TQC.2015.i,
  author =	{Beigi, Salman and K\"{o}nig, Robert},
  title =	{{Front Matter, Table of Contents, Preface, Committees}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{i--xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.i},
  URN =		{urn:nbn:de:0030-drops-55612},
  doi =		{10.4230/LIPIcs.TQC.2015.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Committees}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.1
Oracles with Costs

Authors: Shelby Kimmel, Cedric Yen-Yu Lin, and Han-Hsuan Lin

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.
Cite as

Shelby Kimmel, Cedric Yen-Yu Lin, and Han-Hsuan Lin. Oracles with Costs. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kimmel_et_al:LIPIcs.TQC.2015.1,
  author =	{Kimmel, Shelby and Lin, Cedric Yen-Yu and Lin, Han-Hsuan},
  title =	{{Oracles with Costs}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{1--26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.1},
  URN =		{urn:nbn:de:0030-drops-55459},
  doi =		{10.4230/LIPIcs.TQC.2015.1},
  annote =	{Keywords: Quantum Algorithms, Query Complexity, Amplitude Amplification}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.27
The Resource Theory of Steering

Authors: Rodrigo Gallego and Leandro Aolita

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We present an operational framework for Einstein-Podolsky-Rosen steering as a physical resource. To begin with, we characterize the set of steering non-increasing operations (SNIOs) – i.e., those that do not create steering– on arbitrary-dimensional bipartite systems composed of a quantum subsystem and a black-box device. Next, we introduce the notion of convex steering monotones as the fundamental axiomatic quantifiers of steering. As a convenient example thereof, we present the relative entropy of steering. In addition, we prove that two previously proposed quantifiers, the steerable weight and the robustness of steering, are also convex steering monotones. To end up with, for minimal-dimensional systems, we establish, on the one hand, necessary and sufficient conditions for pure-state steering conversions under stochastic SNIOs and prove, on the other hand, the non-existence of steering bits, i.e., measure-independent maximally steerable states from which all states can be obtained by means of the free operations. Our findings reveal unexpected aspects of steering and lay foundations for further resource-theory approaches, with potential implications in Bell non-locality.
Cite as

Rodrigo Gallego and Leandro Aolita. The Resource Theory of Steering. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 27-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{gallego_et_al:LIPIcs.TQC.2015.27,
  author =	{Gallego, Rodrigo and Aolita, Leandro},
  title =	{{The Resource Theory of Steering}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{27--38},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.27},
  URN =		{urn:nbn:de:0030-drops-55461},
  doi =		{10.4230/LIPIcs.TQC.2015.27},
  annote =	{Keywords: Entanglement, EPR-steering, nonlocality, resource theories}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.39
How Many Quantum Correlations Are Not Local?

Authors: Carlos E. González-Guillén, C. Hugo Jiménez, Carlos Palazuelos, and Ignacio Villanueva

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We study how generic is the property of nonlocality among the set of quantum correlations for bipartite dichotomic measurements. To do so, we consider the characterization of these quantum correlations as those of the form gamma = ( < u_i , v_j > )_{i,j=1}^n , where the vectors u_i and v_j are in the unit sphere of a real Hilbert space. The important parameters in this description are the number of vectors n and the dimension of the Hilbert space m. Thus, it is natural to study the probability of a quantum correlation being nonlocal as a function of alpha = m/n , where the previous vectors are independent and uniformly distributed in the unit sphere of R^m. In this situation, our main result shows the existence of two completely different regimes: There exists an alpha_0 > 0 such that if alpha leq alpha_0, then gamma is nonlocal with probability tending to 1 as n rightarrow infty. On the other hand, if alpha geq 2 then gamma is local with probability tending to 1 as n rightarrow infty.
Cite as

Carlos E. González-Guillén, C. Hugo Jiménez, Carlos Palazuelos, and Ignacio Villanueva. How Many Quantum Correlations Are Not Local?. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 39-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{gonzalezguillen_et_al:LIPIcs.TQC.2015.39,
  author =	{Gonz\'{a}lez-Guill\'{e}n, Carlos E. and Jim\'{e}nez, C. Hugo and Palazuelos, Carlos and Villanueva, Ignacio},
  title =	{{How Many Quantum Correlations Are Not Local?}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{39--47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.39},
  URN =		{urn:nbn:de:0030-drops-55475},
  doi =		{10.4230/LIPIcs.TQC.2015.39},
  annote =	{Keywords: nonlocality, quantum correlations, Bell inequalities, random matrices}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.48
The Spin-2 AKLT State on the Square Lattice is Universal for Measurement-based Quantum Computation

Authors: Tzu-Chieh Wei and Robert Raussendorf

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
One-way quantum computation was first invented using the cluster state. Since then graph states, the generalization of the cluster state, were investigated and understood when they would enable such a measurement-based approach for quantum computation. Are there any other family of states, i.e., states with different entanglement structures, that can also serve as the universal resource for quantum computation? Recent study shows that the Affleck-Kennedy-Lieb-Tasaki (AKLT) states also provide a useful source. Here, we show that the spin-2 state on the square lattice is a universal resource for measurement-based quantum computation. We employ a POVM on all sites that convert the local 5-level system to 2-level, and the post-POVM state is a graph state, whose graph is in general non-planar. We then follow with another round of measurement to recover the planarity of the graphs by thinning. The resultant typical graphs are shown to reside in the supercritical phase of percolation via Monte Carlo simulations and the associated graph states are universal, implying the AKLT state is also universal.
Cite as

Tzu-Chieh Wei and Robert Raussendorf. The Spin-2 AKLT State on the Square Lattice is Universal for Measurement-based Quantum Computation. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 48-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{wei_et_al:LIPIcs.TQC.2015.48,
  author =	{Wei, Tzu-Chieh and Raussendorf, Robert},
  title =	{{The Spin-2 AKLT State on the Square Lattice is Universal for Measurement-based Quantum Computation}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{48--63},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.48},
  URN =		{urn:nbn:de:0030-drops-55484},
  doi =		{10.4230/LIPIcs.TQC.2015.48},
  annote =	{Keywords: Measurement-based quantum computation, AKLT state, graph state, percolation}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.64
Quantum Capacity Can Be Greater Than Private Information for Arbitrarily Many Uses

Authors: David Elkouss and Sergii Strelchuk

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
The quantum capacity of a quantum channel is always smaller than the capacity of the channel for private communication. However, both quantities are given by the infinite regularization of respectively the coherent and the private information. Here, we construct a family of channels for which the private and coherent information can remain strictly superadditive for unbounded number of uses. We prove this by showing that the coherent information is strictly larger than the private information of a smaller number of uses of the channel. It turns out that even though the quantum capacity is upper bounded by the private capacity, the non-regularized quantities can be interleaved. From an operational point of view, the private capacity can be used for gauging the practical value of quantum channels for secure communication and, consequently, for key distribution. We thus show that in order to evaluate the interest a channel for this task it is necessary to optimize the private information over an unlimited number of uses of the channel.
Cite as

David Elkouss and Sergii Strelchuk. Quantum Capacity Can Be Greater Than Private Information for Arbitrarily Many Uses. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 64-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{elkouss_et_al:LIPIcs.TQC.2015.64,
  author =	{Elkouss, David and Strelchuk, Sergii},
  title =	{{Quantum Capacity Can Be Greater Than Private Information for Arbitrarily Many Uses}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{64--72},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.64},
  URN =		{urn:nbn:de:0030-drops-55491},
  doi =		{10.4230/LIPIcs.TQC.2015.64},
  annote =	{Keywords: Quantum channels, capacity, private information}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.73
Semidefinite Programs for Randomness Extractors

Authors: Mario Berta, Omar Fawzi, and Volkher B. Scholz

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
Randomness extractors are an important building block for classical and quantum cryptography. However, for many applications it is crucial that the extractors are quantum-proof, i.e., that they work even in the presence of quantum adversaries. In general, quantum-proof extractors are poorly understood and we would like to argue that in the same way as Bell inequalities (multiprover games) and communication complexity, the setting of randomness extractors provides a operationally useful framework for studying the power and limitations of a quantum memory compared to a classical one. We start by recalling how to phrase the extractor property as a quadratic program with linear constraints. We then construct a semidefinite programming (SDP) relaxation for this program that is tight for some extractor constructions. Moreover, we show that this SDP relaxation is even sufficient to certify quantum-proof extractors. This gives a unifying approach to understand the stability properties of extractors against quantum adversaries. Finally, we analyze the limitations of this SDP relaxation.
Cite as

Mario Berta, Omar Fawzi, and Volkher B. Scholz. Semidefinite Programs for Randomness Extractors. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 73-91, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{berta_et_al:LIPIcs.TQC.2015.73,
  author =	{Berta, Mario and Fawzi, Omar and Scholz, Volkher B.},
  title =	{{Semidefinite Programs for Randomness Extractors}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{73--91},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.73},
  URN =		{urn:nbn:de:0030-drops-55507},
  doi =		{10.4230/LIPIcs.TQC.2015.73},
  annote =	{Keywords: Randomness Extractors, Quantum adversaries, Semidefinite programs}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.92
New Constructions for Quantum Money

Authors: Marios Georgiou and Iordanis Kerenidis

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We propose an information theoretically secure secret-key quantum money scheme in which the verification of a coin is classical and consists of only one round; namely, a classical query from the user to the bank and an accept/reject answer from the bank to the user. A coin can be verified polynomially (on the number of its qubits) many times before it expires. Our scheme is an improvement on Gavinsky's scheme [Gavinsky, Computational Complexity, 2012], where three rounds of interaction are needed and is based on the notion of quantum retrieval games. Moreover, we propose a public-key quantum money scheme which uses one-time memories as a building block and is computationally secure in the random oracle model. This construction is derived naturally from our secret-key scheme using the fact that one-time memories are a special case of quantum retrieval games.
Cite as

Marios Georgiou and Iordanis Kerenidis. New Constructions for Quantum Money. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 92-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{georgiou_et_al:LIPIcs.TQC.2015.92,
  author =	{Georgiou, Marios and Kerenidis, Iordanis},
  title =	{{New Constructions for Quantum Money}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{92--110},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.92},
  URN =		{urn:nbn:de:0030-drops-55510},
  doi =		{10.4230/LIPIcs.TQC.2015.92},
  annote =	{Keywords: Quantum Money, Quantum Cryptography, Quantum Retrieval Games}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.111
Decoherence in Open Majorana Systems

Authors: Earl T. Campbell

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
Coupling to a thermal bath leads to decoherence of stored quantum information. For a system of Gaussian fermions, the fermionic analog of linear or Gaussian optics, these dynamics can be elegantly and efficiently described by evolution of the system's covariance matrix. Taking both system and bath to be Gaussian fermionic, we observe that decoherence occurs at a rate that is independent of the bath temperature. Furthermore, we also consider a weak coupling regime where the dynamics are Markovian. We present a microscopic derivation of Markovian master equations entirely in the language of covariance matrices, where temperature independence remains manifest. This is radically different from behaviour seen in other scenarios, such as when fermions interact with a bosonic bath. Our analysis applies to many Majorana fermion systems that have been heralded as very robust, topologically protected, qubits. In these systems, it has been claimed that thermal decoherence can be exponentially suppressed by reducing temperature, but we find Gaussian decoherence cannot be cooled away.
Cite as

Earl T. Campbell. Decoherence in Open Majorana Systems. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 111-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{campbell:LIPIcs.TQC.2015.111,
  author =	{Campbell, Earl T.},
  title =	{{Decoherence in Open Majorana Systems}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{111--126},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.111},
  URN =		{urn:nbn:de:0030-drops-55528},
  doi =		{10.4230/LIPIcs.TQC.2015.111},
  annote =	{Keywords: Majorana, Topological, Gaussian, Thermalization, Decoherence}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.127
On the Closure of the Completely Positive Semidefinite Cone and Linear Approximations to Quantum Colorings

Authors: Sabine Burgdorf, Monique Laurent, and Teresa Piovesan

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We investigate structural properties of the completely positive semidefinite cone CS^n_+, consisting of all the n x n symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone has been introduced to model quantum graph parameters as conic optimization problems. Recently it has also been used to characterize the set Q of bipartite quantum correlations, as projection of an affine section of it. We have two main results concerning the structure of the completely positive semidefinite cone, namely about its interior and about its closure. On the one hand we construct a hierarchy of polyhedral cones which covers the interior of CS^n_+, which we use for computing some variants of the quantum chromatic number by way of a linear program. On the other hand we give an explicit description of the closure of the completely positive semidefinite cone, by showing that it consists of all matrices admitting a Gram representation in the tracial ultraproduct of matrix algebras.
Cite as

Sabine Burgdorf, Monique Laurent, and Teresa Piovesan. On the Closure of the Completely Positive Semidefinite Cone and Linear Approximations to Quantum Colorings. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 127-146, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{burgdorf_et_al:LIPIcs.TQC.2015.127,
  author =	{Burgdorf, Sabine and Laurent, Monique and Piovesan, Teresa},
  title =	{{On the Closure of the Completely Positive Semidefinite Cone and Linear Approximations to Quantum Colorings}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{127--146},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.127},
  URN =		{urn:nbn:de:0030-drops-55537},
  doi =		{10.4230/LIPIcs.TQC.2015.127},
  annote =	{Keywords: Quantum graph parameters, Trace nonnegative polynomials, Copositive cone, Chromatic number, Quantum Entanglement, Nonlocal games, Von Neumann algebra}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.147
Making Existential-unforgeable Signatures Strongly Unforgeable in the Quantum Random-oracle Model

Authors: Edward Eaton and Fang Song

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a new message is hard, it is infeasible as well to produce a new signature on a message for which the adversary has seen valid signatures before. Strongly unforgeable signatures are useful both in practice and as a building block in many cryptographic constructions. This work investigates a generic transformation that compiles any existential-unforgeable scheme into a strongly unforgeable one, which was proposed by Teranishi et al. [Teranishi/Oyama/Ogata, Cryptology-Indocrypt 2006] and was proven in the classical random-oracle model. Our main contribution is showing that the transformation also works against quantum adversaries in the quantum random-oracle model. We develop proof techniques such as adaptively programming a quantum random-oracle in a new setting, which could be of independent interest. Applying the transformation to an existential-unforgeable signature scheme due to Cash et al. [Cash/Hofheinz/Kiltz/Peikert, J. of Cryptology 2012], which can be shown to be quantum-secure assuming certain lattice problems are hard for quantum computers, we get an efficient quantum-secure strongly unforgeable signature scheme in the quantum random-oracle model.
Cite as

Edward Eaton and Fang Song. Making Existential-unforgeable Signatures Strongly Unforgeable in the Quantum Random-oracle Model. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 147-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{eaton_et_al:LIPIcs.TQC.2015.147,
  author =	{Eaton, Edward and Song, Fang},
  title =	{{Making Existential-unforgeable Signatures Strongly Unforgeable in the Quantum Random-oracle Model}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{147--162},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.147},
  URN =		{urn:nbn:de:0030-drops-55540},
  doi =		{10.4230/LIPIcs.TQC.2015.147},
  annote =	{Keywords: digital signatures, strongly unforgeable, quantum random-oracle, lattices}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.163
A Universal Adiabatic Quantum Query Algorithm

Authors: Mathieu Brandeho and Jérémie Roland

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
Quantum query complexity is known to be characterized by the so-called quantum adversary bound. While this result has been proved in the standard discrete-time model of quantum computation, it also holds for continuous-time (or Hamiltonian-based) quantum computation, due to a known equivalence between these two query complexity models. In this work, we revisit this result by providing a direct proof in the continuous-time model. One originality of our proof is that it draws new connections between the adversary bound, a modern technique of theoretical computer science, and early theorems of quantum mechanics. Indeed, the proof of the lower bound is based on Ehrenfest's theorem, while the upper bound relies on the adiabatic theorem, as it goes by constructing a universal adiabatic quantum query algorithm. Another originality is that we use for the first time in the context of quantum computation a version of the adiabatic theorem that does not require a spectral gap.
Cite as

Mathieu Brandeho and Jérémie Roland. A Universal Adiabatic Quantum Query Algorithm. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 163-179, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{brandeho_et_al:LIPIcs.TQC.2015.163,
  author =	{Brandeho, Mathieu and Roland, J\'{e}r\'{e}mie},
  title =	{{A Universal Adiabatic Quantum Query Algorithm}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{163--179},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.163},
  URN =		{urn:nbn:de:0030-drops-55556},
  doi =		{10.4230/LIPIcs.TQC.2015.163},
  annote =	{Keywords: Quantum Algorithms, Query Complexity, Adiabatic Quantum Computation, Adversary Method}
}
  • Refine by Author
  • 4 Beigi, Salman
  • 2 Piovesan, Teresa
  • 2 Winter, Andreas
  • 1 Aolita, Leandro
  • 1 Arunachalam, Srinivasan
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Information theory
  • 1 Mathematics of computing → Probability and statistics
  • 1 Theory of computation → Expander graphs and randomness extractors

  • Refine by Keyword
  • 2 Quantum Algorithms
  • 2 Query Complexity
  • 2 capacity
  • 2 nonlocality
  • 1 AKLT state
  • Show More...

  • Refine by Type
  • 20 document
  • 1 volume

  • Refine by Publication Year
  • 19 2015
  • 1 2013
  • 1 2018

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