2 Search Results for "Fujii, Keisuke"


Document
Average-Case Quantum Advantage with Shallow Circuits

Authors: François Le Gall

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
Recently Bravyi, Gosset and König (Science 2018) proved an unconditional separation between the computational powers of small-depth quantum and classical circuits for a relation. In this paper we show a similar separation in the average-case setting that gives stronger evidence of the superiority of small-depth quantum computation: we construct a computational task that can be solved on all inputs by a quantum circuit of constant depth with bounded-fanin gates (a "shallow" quantum circuit) and show that any classical circuit with bounded-fanin gates solving this problem on a non-negligible fraction of the inputs must have logarithmic depth. Our results are obtained by introducing a technique to create quantum states exhibiting global quantum correlations from any graph, via a construction that we call the extended graph. Similar results have been very recently (and independently) obtained by Coudron, Stark and Vidick (arXiv:1810.04233}), and Bene Watts, Kothari, Schaeffer and Tal (STOC 2019).

Cite as

François Le Gall. Average-Case Quantum Advantage with Shallow Circuits. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{legall:LIPIcs.CCC.2019.21,
  author =	{Le Gall, Fran\c{c}ois},
  title =	{{Average-Case Quantum Advantage with Shallow Circuits}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.21},
  URN =		{urn:nbn:de:0030-drops-108432},
  doi =		{10.4230/LIPIcs.CCC.2019.21},
  annote =	{Keywords: Quantum computing, circuit complexity, constant-depth circuits}
}
Document
Power of Quantum Computation with Few Clean Qubits

Authors: Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani

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


Abstract
This paper investigates the power of polynomial-time quantum computation in which only a very limited number of qubits are initially clean in the |0> state, and all the remaining qubits are initially in the totally mixed state. No initializations of qubits are allowed during the computation, nor are intermediate measurements. The main contribution of this paper is to develop unexpectedly strong error-reduction methods for such quantum computations that simultaneously reduce the number of necessary clean qubits. It is proved that any problem solvable by a polynomialtime quantum computation with one-sided bounded error that uses logarithmically many clean qubits is also solvable with exponentially small one-sided error using just two clean qubits, and with polynomially small one-sided error using just one clean qubit. It is further proved in the twosided-error case that any problem solvable by such a computation with a constant gap between completeness and soundness using logarithmically many clean qubits is also solvable with exponentially small two-sided error using just two clean qubits. If only one clean qubit is available, the problem is again still solvable with exponentially small error in one of the completeness and soundness and with polynomially small error in the other. An immediate consequence is that the Trace Estimation problem defined with fixed constant threshold parameters is complete for BQ_{[1]}P and BQ_{log}P, the classes of problems solvable by polynomial-time quantum computations with completeness 2/3 and soundness 1/3 using just one and logarithmically many clean qubits, respectively. The techniques used for proving the error-reduction results may be of independent interest in themselves, and one of the technical tools can also be used to show the hardness of weak classical simulations of one-clean-qubit computations (i.e., DQC1 computations).

Cite as

Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani. Power of Quantum Computation with Few Clean Qubits. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{fujii_et_al:LIPIcs.ICALP.2016.13,
  author =	{Fujii, Keisuke and Kobayashi, Hirotada and Morimae, Tomoyuki and Nishimura, Harumichi and Tamate, Shuhei and Tani, Seiichiro},
  title =	{{Power of Quantum Computation with Few Clean Qubits}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{13:1--13: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.13},
  URN =		{urn:nbn:de:0030-drops-62960},
  doi =		{10.4230/LIPIcs.ICALP.2016.13},
  annote =	{Keywords: DQC1, quantum computing, complete problems, error reduction}
}
  • Refine by Author
  • 1 Fujii, Keisuke
  • 1 Kobayashi, Hirotada
  • 1 Le Gall, François
  • 1 Morimae, Tomoyuki
  • 1 Nishimura, Harumichi
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Quantum computation theory

  • Refine by Keyword
  • 1 DQC1
  • 1 Quantum computing
  • 1 circuit complexity
  • 1 complete problems
  • 1 constant-depth circuits
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2019

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