Search Results

Documents authored by Jeffery, Stacey

Document
DOI: 10.4230/LIPIcs.ESA.2023.10
(No) Quantum Space-Time Tradeoff for USTCON

Authors: Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Undirected st-connectivity is important both for its applications in network problems, and for its theoretical connections with logspace complexity. Classically, a long line of work led to a time-space tradeoff of T = Õ(n²/S) for any S such that S = Ω(log(n)) and S = O(n²/m). Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time Õ(n) and space O(log(n)) simultaneously. This improves on previous results, which required either O(log(n)) space and Õ(n^{1.5}) time, or Õ(n) space and time. To complement this, we show that there is a nontrivial time-space tradeoff when given a lower bound on the spectral gap of a corresponding random walk.
Cite as

Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter. (No) Quantum Space-Time Tradeoff for USTCON. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.ESA.2023.10,
  author =	{Apers, Simon and Jeffery, Stacey and Pass, Galina and Walter, Michael},
  title =	{{(No) Quantum Space-Time Tradeoff for USTCON}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.10},
  URN =		{urn:nbn:de:0030-drops-186636},
  doi =		{10.4230/LIPIcs.ESA.2023.10},
  annote =	{Keywords: Undirected st-connectivity, quantum walks, time-space tradeoff}
}
Document
DOI: 10.4230/LIPIcs.TQC.2023.5
Quantum Algorithm for Path-Edge Sampling

Authors: Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the query complexity of detecting a path between s and t. We use this path sampling algorithm as a subroutine for st-path finding and st-cut-set finding algorithms in some specific cases. Our main technical contribution is an algorithm for generating a quantum state that is proportional to the positive witness vector of a span program.
Cite as

Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum Algorithm for Path-Edge Sampling. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 5:1-5:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jeffery_et_al:LIPIcs.TQC.2023.5,
  author =	{Jeffery, Stacey and Kimmel, Shelby and Piedrafita, Alvaro},
  title =	{{Quantum Algorithm for Path-Edge Sampling}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{5:1--5:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.5},
  URN =		{urn:nbn:de:0030-drops-183151},
  doi =		{10.4230/LIPIcs.TQC.2023.5},
  annote =	{Keywords: Algorithm design and analysis, Query complexity, Graph algorithms, Span program algorithm, Path finding, Path detection}
}
Document
DOI: 10.4230/DagRep.11.9.64
Quantum Cryptanalysis (Dagstuhl Seminar 21421)

Authors: Stacey Jeffery, Michele Mosca, Maria Naya-Plasencia, and Rainer Steinwandt

Published in: Dagstuhl Reports, Volume 11, Issue 9 (2022)

Abstract
This seminar report documents the program and the outcomes of Dagstuhl Seminar 21421 Quantum Cryptanalysis. The seminar took place in a hybrid format in Fall 2021. The report starts out with the motivation and comments on the organization of this instance of the Dagstuhl Seminar series on {Quantum Cryptanalysis}, followed by abstracts of presentations. The presentation abstracts were provided by seminar participants.
Cite as

Stacey Jeffery, Michele Mosca, Maria Naya-Plasencia, and Rainer Steinwandt. Quantum Cryptanalysis (Dagstuhl Seminar 21421). In Dagstuhl Reports, Volume 11, Issue 9, pp. 64-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{jeffery_et_al:DagRep.11.9.64,
  author =	{Jeffery, Stacey and Mosca, Michele and Naya-Plasencia, Maria and Steinwandt, Rainer},
  title =	{{Quantum Cryptanalysis (Dagstuhl Seminar 21421)}},
  pages =	{64--79},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{9},
  editor =	{Jeffery, Stacey and Mosca, Michele and Naya-Plasencia, Maria and Steinwandt, Rainer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.9.64},
  URN =		{urn:nbn:de:0030-drops-159187},
  doi =		{10.4230/DagRep.11.9.64},
  annote =	{Keywords: computational algebra, post-quantum cryptography, quantum computing, quantum resource estimation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.6
A Unified Framework of Quantum Walk Search

Authors: Simon Apers, András Gilyén, and Stacey Jeffery

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.
Cite as

Simon Apers, András Gilyén, and Stacey Jeffery. A Unified Framework of Quantum Walk Search. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.STACS.2021.6,
  author =	{Apers, Simon and Gily\'{e}n, Andr\'{a}s and Jeffery, Stacey},
  title =	{{A Unified Framework of Quantum Walk Search}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.6},
  URN =		{urn:nbn:de:0030-drops-136511},
  doi =		{10.4230/LIPIcs.STACS.2021.6},
  annote =	{Keywords: Quantum Algorithms, Quantum Walks, Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.26
Span Programs and Quantum Time Complexity

Authors: Arjan Cornelissen, Stacey Jeffery, Maris Ozols, and Alvaro Piedrafita

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Span programs are an important model of quantum computation due to their correspondence with quantum query and space complexity. While the query complexity of quantum algorithms obtained from span programs is well-understood, it is not generally clear how to implement certain query-independent operations in a time-efficient manner. In this work, we prove an analogous connection for quantum time complexity. In particular, we show how to convert a sufficiently-structured quantum algorithm for f with time complexity T into a span program for f such that it compiles back into a quantum algorithm for f with time complexity 𝒪̃(T). This shows that for span programs derived from algorithms with a time-efficient implementation, we can preserve the time efficiency when implementing the span program, which means that span programs capture time, query and space complexities and are a complete model of quantum algorithms. One practical advantage of being able to convert quantum algorithms to span programs in a way that preserves time complexity is that span programs compose very nicely. We demonstrate this by improving Ambainis’s variable-time quantum search result using our construction through a span program composition for the OR function.
Cite as

Arjan Cornelissen, Stacey Jeffery, Maris Ozols, and Alvaro Piedrafita. Span Programs and Quantum Time Complexity. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cornelissen_et_al:LIPIcs.MFCS.2020.26,
  author =	{Cornelissen, Arjan and Jeffery, Stacey and Ozols, Maris and Piedrafita, Alvaro},
  title =	{{Span Programs and Quantum Time Complexity}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.26},
  URN =		{urn:nbn:de:0030-drops-126947},
  doi =		{10.4230/LIPIcs.MFCS.2020.26},
  annote =	{Keywords: quantum query algorithms, span programs, variable-time quantum search}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.4
Span Programs and Quantum Space Complexity

Authors: Stacey Jeffery

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
While quantum computers hold the promise of significant computational speedups, the limited size of early quantum machines motivates the study of space-bounded quantum computation. We relate the quantum space complexity of computing a function f with one-sided error to the logarithm of its span program size, a classical quantity that is well-studied in attempts to prove formula size lower bounds. In the more natural bounded error model, we show that the amount of space needed for a unitary quantum algorithm to compute f with bounded (two-sided) error is lower bounded by the logarithm of its approximate span program size. Approximate span programs were introduced in the field of quantum algorithms but not studied classically. However, the approximate span program size of a function is a natural generalization of its span program size. While no non-trivial lower bound is known on the span program size (or approximate span program size) of any concrete function, a number of lower bounds are known on the monotone span program size. We show that the approximate monotone span program size of f is a lower bound on the space needed by quantum algorithms of a particular form, called monotone phase estimation algorithms, to compute f. We then give the first non-trivial lower bound on the approximate span program size of an explicit function.
Cite as

Stacey Jeffery. Span Programs and Quantum Space Complexity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 4:1-4:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jeffery:LIPIcs.ITCS.2020.4,
  author =	{Jeffery, Stacey},
  title =	{{Span Programs and Quantum Space Complexity}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{4:1--4:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.4},
  URN =		{urn:nbn:de:0030-drops-116896},
  doi =		{10.4230/LIPIcs.ITCS.2020.4},
  annote =	{Keywords: Quantum space complexity, span programs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.33
The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation

Authors: Shantanav Chakraborty, András Gilyén, and Stacey Jeffery

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

Abstract
We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.
Cite as

Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ICALP.2019.33,
  author =	{Chakraborty, Shantanav and Gily\'{e}n, Andr\'{a}s and Jeffery, Stacey},
  title =	{{The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{33:1--33: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.33},
  URN =		{urn:nbn:de:0030-drops-106092},
  doi =		{10.4230/LIPIcs.ICALP.2019.33},
  annote =	{Keywords: Quantum algorithms, Hamiltonian simulation, Quantum machine learning}
}
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.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.ESA.2018.49
Quantum Algorithms for Connectivity and Related Problems

Authors: Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita

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

Abstract
An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa>1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.
Cite as

Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum Algorithms for Connectivity and Related Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jarret_et_al:LIPIcs.ESA.2018.49,
  author =	{Jarret, Michael and Jeffery, Stacey and Kimmel, Shelby and Piedrafita, Alvaro},
  title =	{{Quantum Algorithms for Connectivity and Related Problems}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{49:1--49:13},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.49},
  URN =		{urn:nbn:de:0030-drops-95121},
  doi =		{10.4230/LIPIcs.ESA.2018.49},
  annote =	{Keywords: Electrical networks, Quantum algorithms, Span programs, Connectivity, Graph theory}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.TQC.2018
LIPIcs, Volume 111, TQC'18, Complete Volume

Authors: Stacey Jeffery

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

Abstract
LIPIcs, Volume 111, TQC'18, Complete Volume
Cite as

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

Copy BibTex To Clipboard

@Proceedings{jeffery:LIPIcs.TQC.2018,
  title =	{{LIPIcs, Volume 111, TQC'18, Complete Volume}},
  booktitle =	{13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2018},
  URN =		{urn:nbn:de:0030-drops-93004},
  doi =		{10.4230/LIPIcs.TQC.2018},
  annote =	{Keywords: Theory of computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TQC.2018.0
Front Matter, Table of Contents

Authors: Stacey Jeffery

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

Abstract
Front Matter, Table of Contents
Cite as

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

Copy BibTex To Clipboard

@InProceedings{jeffery:LIPIcs.TQC.2018.0,
  author =	{Jeffery, Stacey},
  title =	{{Front Matter, Table of Contents}},
  booktitle =	{13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)},
  pages =	{0:i--0:vi},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2018.0},
  URN =		{urn:nbn:de:0030-drops-92476},
  doi =		{10.4230/LIPIcs.TQC.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.12
Approximate Span Programs

Authors: Tsuyoshi Ito and Stacey Jeffery

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Span programs are a model of computation that have been used to design quantum algorithms, mainly in the query model. It is known that for any decision problem, there exists a span program that leads to an algorithm with optimal quantum query complexity, however finding such an algorithm is generally challenging. In this work, we consider new ways of designing quantum algorithms using span programs. We show how any span program that decides a problem f can also be used to decide "property testing" versions of the function f, or more generally, approximate a quantity called the span program witness size, which is some property of the input related to f. For example, using our techniques, the span program for OR, which can be used to design an optimal algorithm for the OR function, can also be used to design optimal algorithms for: threshold functions, in which we want to decide if the Hamming weight of a string is above a threshold, or far below, given the promise that one of these is true; and approximate counting, in which we want to estimate the Hamming weight of the input up to some desired accuracy. We achieve these results by relaxing the requirement that 1-inputs hit some target exactly in the span program, which could potentially make design of span programs significantly easier. In addition, we give an exposition of span program structure, which increases the general understanding of this important model. One implication of this is alternative algorithms for estimating the witness size when the phase gap of a certain unitary can be lower bounded. We show how to lower bound this phase gap in certain cases. As an application, we give the first upper bounds in the adjacency query model on the quantum time complexity of estimating the effective resistance between s and t, R_{s,t}(G). For this problem we obtain ~O(1/epsilon^{3/2}*n*sqrt(R_{s,t}(G)), using O(log(n)) space. In addition, when mu is a lower bound on lambda_2(G), by our phase gap lower bound, we can obtain an upper bound of ~O(1/epsilon*n*sqrt(R){s,t}(G)/mu)) for estimating effective resistance, also using O(log(n)) space.
Cite as

Tsuyoshi Ito and Stacey Jeffery. Approximate Span Programs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.ICALP.2016.12,
  author =	{Ito, Tsuyoshi and Jeffery, Stacey},
  title =	{{Approximate Span Programs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.12},
  URN =		{urn:nbn:de:0030-drops-62956},
  doi =		{10.4230/LIPIcs.ICALP.2016.12},
  annote =	{Keywords: Quantum algorithms, span programs, quantum query complexity, effective resistance}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.54
Quantum Communication Complexity of Distributed Set Joins

Authors: Stacey Jeffery and François Le Gall

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the natural model of (classical) two-party communication complexity and obtained tight bounds for the complexity of several important distributed set joins. In this paper we initiate the study of the quantum communication complexity of distributed set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which corresponds to computing the composition join of two databases, showing that the product of two n times n Boolean matrices, each owned by one of two respective parties, can be computed with widetilde-O(sqrt{n} ell^{3/4}) qubits of communication, where ell denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is widetilde-Theta(n sqrt{ell}), our quantum algorithm outperforms classical protocols whenever the output matrix is sparse. We also show a quantum lower bound and a matching classical upper bound on the communication complexity of distributed matrix multiplication over F_2. Besides their applications to database theory, the communication complexity of set joins is interesting due to its connections to direct product theorems in communication complexity. In this work we also introduce a notion of all-pairs product theorem, and relate this notion to standard direct product theorems in communication complexity.
Cite as

Stacey Jeffery and François Le Gall. Quantum Communication Complexity of Distributed Set Joins. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jeffery_et_al:LIPIcs.MFCS.2016.54,
  author =	{Jeffery, Stacey and Le Gall, Fran\c{c}ois},
  title =	{{Quantum Communication Complexity of Distributed Set Joins}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.54},
  URN =		{urn:nbn:de:0030-drops-64663},
  doi =		{10.4230/LIPIcs.MFCS.2016.54},
  annote =	{Keywords: quantum communication complexity, distributed quantum computing, database joins}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.141
Circuit Obfuscation Using Braids

Authors: Gorjan Alagic, Stacey Jeffery, and Stephen Jordan

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

Abstract
An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mainly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.
Cite as

Gorjan Alagic, Stacey Jeffery, and Stephen Jordan. Circuit Obfuscation Using Braids. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 141-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{alagic_et_al:LIPIcs.TQC.2014.141,
  author =	{Alagic, Gorjan and Jeffery, Stacey and Jordan, Stephen},
  title =	{{Circuit Obfuscation Using Braids}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{141--160},
  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.141},
  URN =		{urn:nbn:de:0030-drops-48135},
  doi =		{10.4230/LIPIcs.TQC.2014.141},
  annote =	{Keywords: obfuscation, cryptography, universality, quantum}
}
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