Search Results

Documents authored by Cornelissen, Arjan

Document
DOI: 10.4230/LIPIcs.TQC.2023.13
Quantum Policy Gradient Algorithms

Authors: Sofiene Jerbi, Arjan Cornelissen, Maris Ozols, and Vedran Dunjko

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

Abstract
Understanding the power and limitations of quantum access to data in machine learning tasks is primordial to assess the potential of quantum computing in artificial intelligence. Previous works have already shown that speed-ups in learning are possible when given quantum access to reinforcement learning environments. Yet, the applicability of quantum algorithms in this setting remains very limited, notably in environments with large state and action spaces. In this work, we design quantum algorithms to train state-of-the-art reinforcement learning policies by exploiting quantum interactions with an environment. However, these algorithms only offer full quadratic speed-ups in sample complexity over their classical analogs when the trained policies satisfy some regularity conditions. Interestingly, we find that reinforcement learning policies derived from parametrized quantum circuits are well-behaved with respect to these conditions, which showcases the benefit of a fully-quantum reinforcement learning framework.
Cite as

Sofiene Jerbi, Arjan Cornelissen, Maris Ozols, and Vedran Dunjko. Quantum Policy Gradient Algorithms. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 13:1-13:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jerbi_et_al:LIPIcs.TQC.2023.13,
  author =	{Jerbi, Sofiene and Cornelissen, Arjan and Ozols, Maris and Dunjko, Vedran},
  title =	{{Quantum Policy Gradient Algorithms}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{13:1--13:24},
  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.13},
  URN =		{urn:nbn:de:0030-drops-183230},
  doi =		{10.4230/LIPIcs.TQC.2023.13},
  annote =	{Keywords: quantum reinforcement learning, policy gradient methods, parametrized quantum circuits}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.15
Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Authors: Arjan Cornelissen, Nikhil S. Mande, and Subhasree Patro

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
We consider the following question in query complexity: Given a classical query algorithm in the form of a decision tree, when does there exist a quantum query algorithm with a speed-up (i.e., that makes fewer queries) over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up in the number of queries. In particular, our results give a bounded-error quantum query algorithm of cost O(√s) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size s. This recovers an O(√n) algorithm for the Search problem, for example. Lin and Lin [Theory of Computing'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor. Their upper bounds are in terms of a quantity which we call the "guessing complexity" of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Information and Computation'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any measure studied in classical complexity theory. We also show a polynomial separation between rank and its natural randomized analog for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to edges of the tree. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are strictly stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes in their construction could yield better upper bounds.
Cite as

Arjan Cornelissen, Nikhil S. Mande, and Subhasree Patro. Improved Quantum Query Upper Bounds Based on Classical Decision Trees. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cornelissen_et_al:LIPIcs.FSTTCS.2022.15,
  author =	{Cornelissen, Arjan and Mande, Nikhil S. and Patro, Subhasree},
  title =	{{Improved Quantum Query Upper Bounds Based on Classical Decision Trees}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.15},
  URN =		{urn:nbn:de:0030-drops-174071},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.15},
  annote =	{Keywords: Quantum Query Complexity, Decision Trees, Decision Tree Rank}
}
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}
}
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