Design of exponential-time quantum algorithms
指数时间量子算法的设计
基本信息
- 批准号：20H04138
- 负责人：
- 金额：$ 11.32万
- 依托单位：
- 依托单位国家：日本
- 项目类别：Grant-in-Aid for Scientific Research (B)
- 财政年份：2020
- 资助国家：日本
- 起止时间：2020-04-01 至 2024-03-31
- 项目状态：已结题
- 来源：
- 关键词：
项目摘要
グラフ彩色問題に対する指数時間量子アルゴリズムを得ることができた。現在知られている最速の古典アルゴリズムは Ω(2^n) 時間で n頂点グラフの彩色数を計算する。本研究では O(1.914^n) 時間で彩色数を計算する量子アルゴリズムを開発した。また、無線通信の問題に対して Grover のアルゴリズムを適用する手法を開発した。
得到了图着色问题的指数时间量子算法。目前已知最快的经典算法可以在 Ω(2^n) 时间内计算 n 顶点图的色数。在这项研究中，我们开发了一种量子算法，可以在 O(1.914^n) 时间内计算色数。我们还开发了一种将 Grover 算法应用于无线通信问题的方法。
项目成果
期刊论文数量（4）
专著数量（0）
科研奖励数量（0）
会议论文数量（0）
专利数量（0）
Quantum supremacy and hardness of estimating output probabilities of quantum circuits
- DOI：10.1109/focs52979.2021.00126
- 发表时间：2021-02
- 期刊：
- 影响因子：0
- 作者：Yasuhiro Kondo;R. Mori;R. Movassagh
- 通讯作者：Yasuhiro Kondo;R. Mori;R. Movassagh
Quantum speedups for dynamic programming on n-dimensional lattice graphs
- DOI：10.4230/lipics.mfcs.2021.50
- 发表时间：2021-04
- 期刊：
- 影响因子：0
- 作者：A. Glos;R. Mori;J. Vihrovs
- 通讯作者：A. Glos;R. Mori;J. Vihrovs
Exponential-time quantum algorithms for graph coloring problems
图着色问题的指数时间量子算法
- DOI：10.1007/s00453-022-00976-2
- 发表时间：2022
- 期刊：
- 影响因子：1.1
- 作者：Liu Chunting;Song Jiangning;Ogata Hiroyuki;Akutsu Tatsuya;Kazuya Shimizu and Ryuhei Mori
- 通讯作者：Kazuya Shimizu and Ryuhei Mori
{{
item.title }}
{{ item.translation_title }}
- DOI：
{{ item.doi }} - 发表时间：
{{ item.publish_year }} - 期刊：
- 影响因子：{{ item.factor }}
- 作者：
{{ item.authors }} - 通讯作者：
{{ item.author }}
数据更新时间：{{ journalArticles.updateTime }}
{{ item.title }}
- 作者：
{{ item.author }}
数据更新时间：{{ monograph.updateTime }}
{{ item.title }}
- 作者：
{{ item.author }}
数据更新时间：{{ sciAawards.updateTime }}
{{ item.title }}
- 作者：
{{ item.author }}
数据更新时间：{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者：
{{ item.author }}
数据更新时间：{{ patent.updateTime }}
森 立平其他文献
5以上の素数次元におけるマジック状態蒸留プロトコルの等価性の条件
素数维度大于或等于 5 的魔态蒸馏协议的等价条件
- DOI：
- 发表时间：
2019 - 期刊：
- 影响因子：0
- 作者：
近藤 泰大;森 立平 - 通讯作者：
森 立平
詳細に規定された非正則LDPC符号アンサンブルのBP復号における漸近的なエラーフロアの解析
明确指定不规则LDPC码系综BP解码中的渐近误差层分析
- DOI：
- 发表时间：
2007 - 期刊：
- 影响因子：0
- 作者：
森 立平;笠井 健太;渋谷 智治;坂庭 好一 - 通讯作者：
坂庭 好一
森 立平的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI：
{{ item.doi }} - 发表时间：
{{ item.publish_year }} - 期刊：
- 影响因子：{{ item.factor }}
- 作者：
{{ item.authors }} - 通讯作者：
{{ item.author }}
{{ truncateString('森 立平', 18)}}的其他基金
通信路分極現象に基づいた誤り訂正符号とその復号法
基于信道极化现象的纠错码及其译码方法
- 批准号：
10J05936 - 财政年份：2010
- 资助金额：
$ 11.32万 - 项目类别：
Grant-in-Aid for JSPS Fellows
相似海外基金
Refining the graph parameter hierarchy for fine-grained algorithms
细化细粒度算法的图参数层次结构
- 批准号：
21K11752 - 财政年份：2021
- 资助金额：
$ 11.32万 - 项目类别：
Grant-in-Aid for Scientific Research (C)
擬似独立性を持つフィードバック点集合問題の提唱とアルゴリズムの開発
提出伪独立的反馈点集问题并开发算法
- 批准号：
20J11259 - 财政年份：2020
- 资助金额：
$ 11.32万 - 项目类别：
Grant-in-Aid for JSPS Fellows
The Ridesharing Problem of Graphs and Its Applications
图的乘车共享问题及其应用
- 批准号：
19K11813 - 财政年份：2019
- 资助金额：
$ 11.32万 - 项目类别：
Grant-in-Aid for Scientific Research (C)
Computational and Quantum-Physical Approach to Graph Optimization and Invariants for Quantum Advantage
图优化的计算和量子物理方法以及量子优势的不变量
- 批准号：
18K19776 - 财政年份：2018
- 资助金额：
$ 11.32万 - 项目类别：
Grant-in-Aid for Challenging Research (Exploratory)
Speeding up FPT algorithms with special tree decompositions
通过特殊的树分解加速 FPT 算法
- 批准号：
18K11168 - 财政年份：2018
- 资助金额：
$ 11.32万 - 项目类别：
Grant-in-Aid for Scientific Research (C)