检索结果-内蒙古大学图书馆

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

COMPUTATIONAL COMPLEXITY 2016年第4期25卷 849-881页

作者： Takahashi, Yasuhiro Tani, Seiichiro NTT Corp NTT Commun Sci Labs Atsugi Kanagawa 2430198 Japan

We study the quantum complexity class of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in , which is an affirmative answer to the question posed by Hoyer and palek. In sharp contrast to the strict hierarchy of the classical complexity classes: , our result with Hoyer and palek's one implies the collapse of the hierarchy of the corresponding quantum ones: . Then, we show that there exists a constant-depth subquadratic-size quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the and circuits for implementing the same operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in , there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a circuit with gates for the quantum Fourier transform.

关键词： Quantum circuit complexity OR function threshold function discrete logarithm algorithm

来源：评论

学校读者我要写书评

暂无评论

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

Collapse of the Hierarchy of Constant-Depth Exact Quantum Ci...

引用

28th Annual IEEE Conference on Computational Complexity (CCC)

作者： Takahashi, Yasuhiro Tani, Seiichiro NTT Corp NTT Commun Sci Labs Tokyo Japan

ISBN: (纸本)9780769549972

We study the quantum complexity class QNC(f)(0) of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in QNC(f)(0), which is an affirmative answer to the question of Hoyer and. Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC0 (sic) AC(0) (sic) TC0, our result with Hoyer and. Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC(f)(0) = QAC(f)(0) = QTC(f)(0). Then, we show that there exists a constant-depth subquadraticsize quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the QNC(f)(0) and QTC(f)(0) circuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC(f)(0), there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC(f)(0) oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC(f)(0) circuit with gates for the quantum Fourier transform.

关键词： quantum circuit OR function threshold function discrete logarithm algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：