未初期化量子ビットを用いた量子回路の計算能力について

• Item type: SIG Technical Reports(1)
• 公開日: 2018-05-18
• タイトル: 未初期化量子ビットを用いた量子回路の計算能力について
• タイトル / 言語: en
• タイトル: Power of Uninitialized Qubits in Shallow Quantum Circuits
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: NTTコミュニケーション科学基礎研究所
• 著者所属: NTTコミュニケーション科学基礎研究所
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories, NTT Corporation
• 著者名: 高橋, 康博; 谷, 誠一郎
• 著者名(英): Yasuhiro, Takahashi; Seiichiro, Tani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We study the computational power of shallow quantum circuits with O (log n) initialized and no(¹) uninitialized ancillary qubits, where n is the input length and the initial state of the uninitialized ancillary qubits is arbitrary. First, we show that such a circuit can compute any symmetric function on n bits that is classically computable in polynomial time. Then, we regard such a circuit as an oracle and show that a polynomial-time classical algorithm with the oracle can estimate the elements of any unitary matrix corresponding to a constant-depth quantum circuit on n qubits. Since it seems unlikely that these tasks can be done with only O (log n) initialized ancillary qubits, our results give evidences that adding uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O (log n) initialized ancillary qubits. Lastly, to understand the limitations of uninitialized ancillary qubits, we focus on near-logarithmic-depth quantum circuits with them and show the impossibility of computing the parity function on n bits. Details can be found in the conference version [19].
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study the computational power of shallow quantum circuits with O (log n) initialized and no(¹) uninitialized ancillary qubits, where n is the input length and the initial state of the uninitialized ancillary qubits is arbitrary. First, we show that such a circuit can compute any symmetric function on n bits that is classically computable in polynomial time. Then, we regard such a circuit as an oracle and show that a polynomial-time classical algorithm with the oracle can estimate the elements of any unitary matrix corresponding to a constant-depth quantum circuit on n qubits. Since it seems unlikely that these tasks can be done with only O (log n) initialized ancillary qubits, our results give evidences that adding uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O (log n) initialized ancillary qubits. Lastly, to understand the limitations of uninitialized ancillary qubits, we focus on near-logarithmic-depth quantum circuits with them and show the impossibility of computing the parity function on n bits. Details can be found in the conference version [19].
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-168, 号 4, p. 1-4, 発行日 2018-05-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会