Search Results

Documents authored by Montanaro, Ashley

Document
DOI: 10.4230/LIPIcs.ITCS.2023.29
Quantum Majority Vote

Authors: Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, and Maris Ozols

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. While it can amplify the correctness of a quantum device with classical output, the analogous procedure for quantum output is not known. We introduce quantum majority vote as the following task: given a product state |ψ_1⟩ ⊗ … ⊗ |ψ_n⟩ where each qubit is in one of two orthogonal states |ψ⟩ or |ψ^⟂⟩, output the majority state. We show that an optimal algorithm for this problem achieves worst-case fidelity of 1/2 + Θ(1/√n). Under the promise that at least 2/3 of the input qubits are in the majority state, the fidelity increases to 1 - Θ(1/n) and approaches 1 as n increases. We also consider the more general problem of computing any symmetric and equivariant Boolean function f: {0,1}ⁿ → {0,1} in an unknown quantum basis, and show that a generalization of our quantum majority vote algorithm is optimal for this task. The optimal parameters for the generalized algorithm and its worst-case fidelity can be determined by a simple linear program of size O(n). The time complexity of the algorithm is O(n⁴ log n) where n is the number of input qubits.
Cite as

Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, and Maris Ozols. Quantum Majority Vote. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, p. 29:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.ITCS.2023.29,
  author =	{Buhrman, Harry and Linden, Noah and Man\v{c}inska, Laura and Montanaro, Ashley and Ozols, Maris},
  title =	{{Quantum Majority Vote}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{29:1--29:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.29},
  URN =		{urn:nbn:de:0030-drops-175321},
  doi =		{10.4230/LIPIcs.ITCS.2023.29},
  annote =	{Keywords: quantum algorithms, quantum majority vote, Schur-Weyl duality}
}
Document
DOI: 10.4230/LIPIcs.TQC.2022.1
Quantum Algorithms for Learning a Hidden Graph

Authors: Ashley Montanaro and Changpeng Shao

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

Abstract
We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model ("OR queries"), the oracle returns whether a given subset of the vertices contains any edges. In the second ("parity queries"), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al. for a "gapped" version of the group testing problem.
Cite as

Ashley Montanaro and Changpeng Shao. Quantum Algorithms for Learning a Hidden Graph. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{montanaro_et_al:LIPIcs.TQC.2022.1,
  author =	{Montanaro, Ashley and Shao, Changpeng},
  title =	{{Quantum Algorithms for Learning a Hidden Graph}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{1:1--1:22},
  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.1},
  URN =		{urn:nbn:de:0030-drops-165081},
  doi =		{10.4230/LIPIcs.TQC.2022.1},
  annote =	{Keywords: Quantum algorithms, query complexity, graphs, combinatorial group testing}
}
Document
DOI: 10.4230/LIPIcs.TQC.2020.1
Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem

Authors: João F. Doriguello and Ashley Montanaro

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
In this work we revisit the Boolean Hidden Matching communication problem, which was the first communication problem in the one-way model to demonstrate an exponential classical-quantum communication separation. In this problem, Alice’s bits are matched into pairs according to a partition that Bob holds. These pairs are compressed using a Parity function and it is promised that the final bit-string is equal either to another bit-string Bob holds, or its complement. The problem is to decide which case is the correct one. Here we generalize the Boolean Hidden Matching problem by replacing the parity function with an arbitrary function f. Efficient communication protocols are presented depending on the sign-degree of f. If its sign-degree is less than or equal to 1, we show an efficient classical protocol. If its sign-degree is less than or equal to 2, we show an efficient quantum protocol. We then completely characterize the classical hardness of all symmetric functions f of sign-degree greater than or equal to 2, except for one family of specific cases. We also prove, via Fourier analysis, a classical lower bound for any function f whose pure high degree is greater than or equal to 2. Similarly, we prove, also via Fourier analysis, a quantum lower bound for any function f whose pure high degree is greater than or equal to 3. These results give a large family of new exponential classical-quantum communication separations.
Cite as

João F. Doriguello and Ashley Montanaro. Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{doriguello_et_al:LIPIcs.TQC.2020.1,
  author =	{Doriguello, Jo\~{a}o F. and Montanaro, Ashley},
  title =	{{Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.1},
  URN =		{urn:nbn:de:0030-drops-120601},
  doi =		{10.4230/LIPIcs.TQC.2020.1},
  annote =	{Keywords: Communication Complexity, Quantum Communication Complexity, Boolean Hidden Matching Problem}
}
Document
DOI: 10.4230/LIPIcs.TQC.2018.4
The Quantum Complexity of Computing Schatten p-norms

Authors: Chris Cade and Ashley Montanaro

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

Abstract
We consider the quantum complexity of computing Schatten p-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating Tr(|A|^p) for a log-local n-qubit Hamiltonian A and p=poly(n), up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph.
Cite as

Chris Cade and Ashley Montanaro. The Quantum Complexity of Computing Schatten p-norms. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 111, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cade_et_al:LIPIcs.TQC.2018.4,
  author =	{Cade, Chris and Montanaro, Ashley},
  title =	{{The Quantum Complexity of Computing Schatten p-norms}},
  booktitle =	{13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)},
  pages =	{4:1--4:20},
  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.4},
  URN =		{urn:nbn:de:0030-drops-92513},
  doi =		{10.4230/LIPIcs.TQC.2018.4},
  annote =	{Keywords: Schatten p-norm, quantum complexity theory, complexity theory, one clean qubit model}
}
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