5 Search Results for "Bravyi, Sergey"

Document
DOI: 10.4230/LIPIcs.TQC.2023.3
Optimal Algorithms for Learning Quantum Phase States

Authors: Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder

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

Abstract
We analyze the complexity of learning n-qubit quantum phase states. A degree-d phase state is defined as a superposition of all 2ⁿ basis vectors x with amplitudes proportional to (-1)^{f(x)}, where f is a degree-d Boolean polynomial over n variables. We show that the sample complexity of learning an unknown degree-d phase state is Θ(n^d) if we allow separable measurements and Θ(n^{d-1}) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime poly(n) (for constant d) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli X and Z bases. We show similar bounds on the sample complexity for learning generalized phase states with complex-valued amplitudes. We further consider learning phase states when f has sparsity-s, degree-d in its 𝔽₂ representation (with sample complexity O(2^d sn)), f has Fourier-degree-t (with sample complexity O(2^{2t})), and learning quadratic phase states with ε-global depolarizing noise (with sample complexity O(n^{1+ε})). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP circuits.
Cite as

Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal Algorithms for Learning Quantum Phase States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 3:1-3:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2023.3,
  author =	{Arunachalam, Srinivasan and Bravyi, Sergey and Dutt, Arkopal and Yoder, Theodore J.},
  title =	{{Optimal Algorithms for Learning Quantum Phase States}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-183139},
  doi =		{10.4230/LIPIcs.TQC.2023.3},
  annote =	{Keywords: Tomography, binary phase states, generalized phase states, IQP circuits}
}
Document
DOI: 10.4230/LIPIcs.TQC.2022.3
The Parametrized Complexity of Quantum Verification

Authors: Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)

Abstract
We initiate the study of parameterized complexity of QMA problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem of parameterized quantum circuit satisfiability, there exists a classical algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates but only polynomially with the system size. This result follows from our main result, that for any Clifford + t T-gate quantum circuit satisfiability problem, the search space of optimal witnesses can be reduced to a stabilizer subspace isomorphic to at most t qubits (independent of the system size). Furthermore, we derive new lower bounds on the T-count of circuit satisfiability instances and the T-count of the W-state assuming the classical exponential time hypothesis (ETH). Lastly, we explore the parameterized complexity of the quantum non-identity check problem.
Cite as

Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman. The Parametrized Complexity of Quantum Verification. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 3:1-3:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2022.3,
  author =	{Arunachalam, Srinivasan and Bravyi, Sergey and Nirkhe, Chinmay and O'Gorman, Bryan},
  title =	{{The Parametrized Complexity of Quantum Verification}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.3},
  URN =		{urn:nbn:de:0030-drops-165104},
  doi =		{10.4230/LIPIcs.TQC.2022.3},
  annote =	{Keywords: parametrized complexity, quantum verification, QMA}
}
Document
DOI: 10.4230/LIPIcs.TQC.2022.9
Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension

Authors: Suchetan Dontha, Shi Jie Samuel Tan, Stephen Smith, Sangheon Choi, and Matthew Coudron

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)

Abstract
We present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x ∈ {0,1}ⁿ, can compute the quantity |<x|C|0^{⊗ n}>|² to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension D. This is an extension of the result [Nolan J. Coble and Matthew Coudron, 2021], which originally proved this result for D = 3. To see why this is interesting, note that, while the D = 1 case of this result follows from a standard use of Matrix Product States, known for decades, the D = 2 case required novel and interesting techniques introduced in [Sergy Bravyi et al., 2020]. Extending to the case D = 3 was even more laborious, and required further new techniques introduced in [Nolan J. Coble and Matthew Coudron, 2021]. Our work here shows that, while handling each new dimension has historically required a new insight, and fixed algorithmic primitive, based on known techniques for D ≤ 3, we can now handle any fixed dimension D > 3. Our algorithm uses the Divide-and-Conquer framework of [Nolan J. Coble and Matthew Coudron, 2021] to approximate the desired quantity via several instantiations of the same problem type, each involving D-dimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the D^{th} dimension is so small that they can effectively be regarded as (D-1)-dimensional problems by absorbing the small width in the D^{th} dimension into the qudit structure at the cost of a moderate increase in runtime. The main technical challenge lies in ensuring that the more involved portions of the recursive circuit decomposition and error analysis from [Nolan J. Coble and Matthew Coudron, 2021] still hold in higher dimensions, which requires small modifications to the analysis in some places. Our work also includes some simplifications, corrections and clarifications of the use of block-encodings within the original classical algorithm in [Nolan J. Coble and Matthew Coudron, 2021].
Cite as

Suchetan Dontha, Shi Jie Samuel Tan, Stephen Smith, Sangheon Choi, and Matthew Coudron. Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 9:1-9:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dontha_et_al:LIPIcs.TQC.2022.9,
  author =	{Dontha, Suchetan and Tan, Shi Jie Samuel and Smith, Stephen and Choi, Sangheon and Coudron, Matthew},
  title =	{{Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.9},
  URN =		{urn:nbn:de:0030-drops-165163},
  doi =		{10.4230/LIPIcs.TQC.2022.9},
  annote =	{Keywords: Low-Depth Quantum Circuits, Matrix Product States, Block-Encoding}
}
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.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.STACS.2010.2450
Quantum Algorithms for Testing Properties of Distributions

Authors: Sergey Bravyi, Aram W. Harrow, and Avinatan Hassidim

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Suppose one has access to oracles generating samples from two unknown probability distributions $p$ and $q$ on some $N$-element set. How many samples does one need to test whether the two distributions are close or far from each other in the $L_1$-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the $L_1$-distance $\|p-q\|_1$ can be estimated with a constant precision using only $O(N^{1/2})$ queries in the quantum settings, whereas classical computers need $\Omega(N^{1-o(1)})$ queries. We also describe quantum algorithms for testing Uniformity and Orthogonality with query complexity $O(N^{1/3})$. The classical query complexity of these problems is known to be $\Omega(N^{1/2})$. A quantum algorithm for testing Uniformity has been recently independently discovered by Chakraborty et al. \cite{CFMW09}.
Cite as

Sergey Bravyi, Aram W. Harrow, and Avinatan Hassidim. Quantum Algorithms for Testing Properties of Distributions. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 131-142, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bravyi_et_al:LIPIcs.STACS.2010.2450,
  author =	{Bravyi, Sergey and Harrow, Aram W. and Hassidim, Avinatan},
  title =	{{Quantum Algorithms for Testing Properties of Distributions}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{131--142},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2450},
  URN =		{urn:nbn:de:0030-drops-24502},
  doi =		{10.4230/LIPIcs.STACS.2010.2450},
  annote =	{Keywords: Quantum computing, property testing, sampling}
}
  • Refine by Author
  • 3 Bravyi, Sergey
  • 2 Arunachalam, Srinivasan
  • 1 Choi, Sangheon
  • 1 Coudron, Matthew
  • 1 Dontha, Suchetan
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Quantum complexity theory
  • 2 Theory of computation → Quantum computation theory
  • 1 Theory of computation → Divide and conquer

  • Refine by Keyword
  • 1 Block-Encoding
  • 1 Classical simulation
  • 1 IQP circuits
  • 1 Low-Depth Quantum Circuits
  • 1 Matrix Product States
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2022
  • 1 2010
  • 1 2019
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact