Search Results

Documents authored by Svore, Krysta M.

Found 2 Possible Name Variants:

Svore, Krysta M.

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.27
Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

Authors: Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.
Cite as

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{brandao_et_al:LIPIcs.ICALP.2019.27,
  author =	{Brand\~{a}o, Fernando G. S. L. and Kalev, Amir and Li, Tongyang and Lin, Cedric Yen-Yu and Svore, Krysta M. and Wu, Xiaodi},
  title =	{{Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.27},
  URN =		{urn:nbn:de:0030-drops-106036},
  doi =		{10.4230/LIPIcs.ICALP.2019.27},
  annote =	{Keywords: quantum algorithms, semidefinite program, convex optimization}
}
Document
DOI: 10.4230/LIPIcs.TQC.2013.235
Distillation of Non-Stabilizer States for Universal Quantum Computation

Authors: Guillaume Duclos-Cianci and Krysta M. Svore

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

Abstract
Magic state distillation is a fundamental technique for realizing fault-tolerant universal quantum computing, and produces high-fidelity Clifford eigenstates, called magic states, which can be used to implement the non-Clifford pi/8 gate. We propose an efficient protocol for distilling other non-stabilizer states that requires only Clifford operations, measurement, and magic states. One critical application of our protocol is efficiently and fault tolerantly implementing arbitrary, non-Clifford, single-qubit rotations in average constant online circuit depth and polylogarithmic (in precision) offline resource cost, resulting in significant improvements over state-of-the-art decomposition techniques. Finally, we show that our protocol is robust to noise in the resource states.
Cite as

Guillaume Duclos-Cianci and Krysta M. Svore. Distillation of Non-Stabilizer States for Universal Quantum Computation. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 235-243, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{ducloscianci_et_al:LIPIcs.TQC.2013.235,
  author =	{Duclos-Cianci, Guillaume and Svore, Krysta M.},
  title =	{{Distillation of Non-Stabilizer States for Universal Quantum Computation}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{235--243},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.235},
  URN =		{urn:nbn:de:0030-drops-43233},
  doi =		{10.4230/LIPIcs.TQC.2013.235},
  annote =	{Keywords: quantum computing, resource estimation, magic state distillation}
}

Svore, Krysta

Document
DOI: 10.4230/DagRep.7.10.1
Quantum Cryptanalysis (Dagstuhl Seminar 17401)

Authors: Michele Mosca, Nicolas Sendrier, Rainer Steinwandt, and Krysta Svore

Published in: Dagstuhl Reports, Volume 7, Issue 10 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17401 "Quantum Cryptanalysis." We start out by outlining the motivation and organizational aspects of the seminar. Thereafter, abstracts of presentations given by seminar participants are provided.
Cite as

Michele Mosca, Nicolas Sendrier, Rainer Steinwandt, and Krysta Svore. Quantum Cryptanalysis (Dagstuhl Seminar 17401). In Dagstuhl Reports, Volume 7, Issue 10, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{mosca_et_al:DagRep.7.10.1,
  author =	{Mosca, Michele and Sendrier, Nicolas and Steinwandt, Rainer and Svore, Krysta},
  title =	{{Quantum Cryptanalysis (Dagstuhl Seminar 17401)}},
  pages =	{1--13},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{10},
  editor =	{Mosca, Michele and Sendrier, Nicolas and Steinwandt, Rainer and Svore, Krysta},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.10.1},
  URN =		{urn:nbn:de:0030-drops-86605},
  doi =		{10.4230/DagRep.7.10.1},
  annote =	{Keywords: computational algebra, post-quantum cryptography, quantum circuit complexity, quantum computing, quantum hardware and resource estimation}
}
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