Power of Quantum Computation with Few Clean Qubits

Medientyp: Sonstige Veröffentlichung; Elektronischer Konferenzbericht; E-Artikel

Titel: Power of Quantum Computation with Few Clean Qubits

Beteiligte: Fujii, Keisuke [VerfasserIn]; Kobayashi, Hirotada [VerfasserIn]; Morimae, Tomoyuki [VerfasserIn]; Nishimura, Harumichi [VerfasserIn]; Tamate, Shuhei [VerfasserIn]; Tani, Seiichiro [VerfasserIn]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016

Sprache: Englisch

DOI: https://doi.org/10.4230/LIPIcs.ICALP.2016.13

Schlagwörter: error reduction ; complete problems ; quantum computing ; DQC1

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: 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).

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: