Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

断熱量子コンピューティングによる巡回セールスマン問題の解法

幹夫 中原, 将光 坂東, 宗 田中

Published Feb 28, 2017• 0 citations
OpenAlex

Abstract

巡回セールスマン問題とは,N 都市と各都市の間の距離が与えられたとき,セールスマンがN都市すべてを1 回づつ訪問し,かつその全距離を最小にする経路を探す問題である.古典的にはすべての可能性を列挙して,その中で最小距離の経路を求めればよいが,それにはN! 程度のステップが必要となる.これはNP 困難とよばれるクラスに属する問題で,N が大きくなると実用的ではない.最近,量子コンピュータを用いて,この問題を解く方法が提案され,注目されている.これは断熱的量子コンピューティングと言われる手法であり,実用的な量子コンピュータが存在すれば,N に関して多項式時間で問題が解けると期待される.実際には古典コンピュータを用いて,シミュレーティッド・アニーリングや量子アニーリングとよばれる手法で問題を解くのであるが,本論文では,教育面に重点を置いて,4 都市の問題を表現するシュレーディンガー方程式を直接解き,解法の原理的デモンストレーションを行う.

Related papers

量子計算 : 新情報技術の必要性と可能性

ロドニー バンミーター, シゲヤ スズキ, ショウタ ナガヤマ +5 more

半導体技術は、半世紀の間、コンピュータの性能向上に貢献することで、重要な経済の牽引役となってきた。しかし、今、その前進を阻む根本的な問題に直面している。より高い性能を持つコンピュータへの一つのアプローチは、量子計算の活用である。慶應義塾湘南藤沢キャンパスのAQUA研究グループでは、実用的な量子コンピュータの実現に向けて、様々な研究を進めている。本論文では、量子計算の基本的な概念とアルゴリズム、量子コンピュータ実現のために解決しなければならない問題について紹介する。

•Jan 1, 2013•0 citations

Topological Quantum Computer のための量子回路設計問題

Byung-Soo Choi

現在,注目されている「エラーに強い」量子計算のスキームであるTopologicalQuantum Computer について,その動作原理を簡単に説明した後,その設計のために必要な最適化問題に関する定式化を行う.

•Jun 1, 2011•0 citations

本論文では,非簡并双-CUMMINGSモデルにおけるエンタングルメント発展を研究した。【JST・京大機械翻訳】

Jiang Shengshan, Feng Lingjuan, Yun‐Jie Xia

•Jan 1, 2016•0 citations

不安定粒子のデコヒ-レンス (第4回『非平衡系の統計物理』シンポジウム)

雅博 森川

東京都文京区大塚 2 -1 -1 電子メール:h i r o ◎p h y s .o c h a .舵. j p Ab s t r a c t 何ら窓意的な粗視化を導入せずに不安定 L e eモデルに対する散逸効果を含んだ有効ハ ミ ル ト ニアンを構成する.in -i n形式の場の理論に基づいた一般化された拓射補正は自動的に不可逆性 と量子相関の自発的崩壊を導 く.特に,この方法を用いた記述によれば,根源的に散逸的な系を 記述するために通常のヒルベル ト 空間を拡張する必要が無い事が分かる. 1 導入 物理学において,マ クロな世界の不可逆性 の理解は最 も魅力的なテーマの 1つである.特に基本的な ミクロな法則か ら不可逆性を整合的に導 くことは物理学の中心的な課題 になっている.不幸にし てほとん どすべての ミクロの法則は厳密 に可逆であって,それ らの単純 な適用か らは不可逆性は決 して得 られない.マクロな不可逆性を導 くよ くある方法 は,は じめか ら外に開いた系 を考えることである 【 1 1 ・つ ま り全体 としては閉 じた系を,着 目す る重要な系 と残 りの環境系に分散す る.そ して この環境系に 関 して粗視化を して着 目す る系の運動を得 るのである.不可逆性 は着 目系か ら環境系-

物性研究•Oct 1, 1997•0 citations

A Numerical Study on a Noisy Order of Channels and Information Quantities

Kai Ou

盗聴通信路符号化などの情報理論的安全性に基づく暗号理論においては,盗聴者が用いる通信路は,正規受信者が用いる通信路よりノイズが多いことが仮定される.しかし,盗聴者の通信路を正確に特定できない場合,想定される通信路の中で一番ノイズが少ない通信路を盗聴者が用いるものとして安全性を確保する必要がある.そのため,通信路を比較するための順序を導入する必要があり,これまでもless noisy order (Korner-Marton, 1975) など,通信路に関する様々な順序が研究されてきた.中でも,二つの通信路W, V が与えられたとき,一方の通信路V が他方の通信路Wにさらにノイズを付加した通信路となる関係W > V (degraded order) は統計的にも重要である(Blackwell-Sherman-Stein, 1951). 本論文では,通信路のノイズに関する順序(degraded order) について二つ観点で数値的な研究を行った.一つは通信路の順序と情報量(相互情報量および相対レニーエントロピー)の関係についての研究であり,もう一つは,順序を判定する効率的なアルゴリズムの開発である. 最初に,通信路の順序と相互情報量および相対レニーエントロピーの関係について数値実験による研究を行った.通信路W と通信路の入力アルファベット上の確率分布P が与えられると,相互情報量I(P;W) が計算できる.相互情報量の単調性(データ処理不等式)より,二つの通信路W, V が順序関係W > V を満たす(V はW よりノイズが多い)ならば,すべての入力分布Pについて,相互情報量の大小関係I(P;W) >_ I(P; V ) が成り立つ.本研究では,この命題の逆が成立するかどうかを調べるため,数値実験により,3 入力3 出力の通信路を多数調べることで反例を探した.その結果,反例として,非常に多くの入力分布P について,相互情報量の大小関係I(P;W) >_ I(P; V ) が成り立つが,順序関係W > V を満たさない例を多数見つけた.相対レニーエントロピーについても同様の単調性が成り立つことが知られている.この場合も同様に,単調性の逆の命題が成立しない多数の反例を見つけた. 次に,二つの通信路W, V が任意に与えられたとき,順序関係W > V が満たされるかどうかを判定する一般的なアルゴリズムの開発を行った.本論文では,通信路W に付加的なノイズU が加わる状況を考え,U を変えて行くことでW とU の合成通信路が通信路V に一致するかどうかを最急降下法により調べた.その際,コスト関数として確率遷移行列の成分の二乗和を用いた.また,付加するノイズU も確率遷移行列である必要がるため,U の行列成分は非負かつ行和は1 でなければならない.本論文では,U を指数分布族により表現することで,確率遷移行列の制約条件を満たしながらコスト関数を最小化するアルゴリズムを開発した.

•Sep 28, 2012•0 citations

人工知能を用いた量子アルゴリズムの探索

大門 俊介, 松下雄一郎

量子コンピュータの実用的計算への応用を目指して、様々な量子アルゴリズムが提案されている。しかしながら現在の不完全な量子コンピュータ上では、従来提案されてきた量子アルゴリズムの実行が困難である場合が多く、より効率的な量子アルゴリズムの発見が求められている。そこで我々は、人工知能に量子計算の大量のデータを学習させることによって、量子アルゴリズムを学習させた。構築した人工知能は、少ないデータから量子計算の規則性を見出し、未知の入力に対しても正しい量子計算手順を出力できることが明らかになった。これは、開発した人工知能が少数のデータに内在する規則性を量子アルゴリズムとして理解し、未知のデータに対しても応用しているということを示している。

•Dec 10, 2024•0 citations
巡回セールスマン問題とは,N 都市と各都市の間の距離が与えられたとき,セールスマンがN都市すべてを1 回づつ訪問し,かつその全距離を最小にする経路を探す問題である.古典的にはすべての可能性を列挙して,その中で最小距離の経路を求めればよいが,それにはN! 程度のステップが必要となる.これはNP 困難とよばれるクラスに属する問題で,N が大きくなると実用的ではない.最近,量子コンピュータを用いて,この問題を解く方法が提案され,注目されている.これは断熱的量子コンピューティングと言われる手法であり,実用的な量子コンピュータが存在すれば,N に関して多項式時間で問題が解けると期待される.実際には古典コンピュータを用いて,シミュレーティッド・アニーリングや量子アニーリングとよばれる手法で問題を解くのであるが,本論文では,教育面に重点を置いて,4 都市の問題を表現するシュレーディンガー方程式を直接解き,解法の原理的デモンストレーションを行う.
半導体技術は、半世紀の間、コンピュータの性能向上に貢献することで、重要な経済の牽引役となってきた。しかし、今、その前進を阻む根本的な問題に直面している。より高い性能を持つコンピュータへの一つのアプローチは、量子計算の活用である。慶應義塾湘南藤沢キャンパスのAQUA研究グループでは、実用的な量子コンピュータの実現に向けて、様々な研究を進めている。本論文では、量子計算の基本的な概念とアルゴリズム、量子コンピュータ実現のために解決しなければならない問題について紹介する。
東京都文京区大塚 2 -1 -1 電子メール:h i r o ◎p h y s .o c h a .舵. j p Ab s t r a c t 何ら窓意的な粗視化を導入せずに不安定 L e eモデルに対する散逸効果を含んだ有効ハ ミ ル ト ニアンを構成する.in -i n形式の場の理論に基づいた一般化された拓射補正は自動的に不可逆性 と量子相関の自発的崩壊を導 く.特に,この方法を用いた記述によれば,根源的に散逸的な系を 記述するために通常のヒルベル ト 空間を拡張する必要が無い事が分かる. 1 導入 物理学において,マ クロな世界の不可逆性 の理解は最 も魅力的なテーマの 1つである.特に基本的な ミクロな法則か ら不可逆性を整合的に導 くことは物理学の中心的な課題 になっている.不幸にし てほとん どすべての ミクロの法則は厳密 に可逆であって,それ らの単純 な適用か らは不可逆性は決 して得 られない.マクロな不可逆性を導 くよ くある方法 は,は じめか ら外に開いた系 を考えることである 【 1 1 ・つ ま り全体 としては閉 じた系を,着 目す る重要な系 と残 りの環境系に分散す る.そ して この環境系に 関 して粗視化を して着 目す る系の運動を得 るのである.不可逆性 は着 目系か ら環境系-
盗聴通信路符号化などの情報理論的安全性に基づく暗号理論においては,盗聴者が用いる通信路は,正規受信者が用いる通信路よりノイズが多いことが仮定される.しかし,盗聴者の通信路を正確に特定できない場合,想定される通信路の中で一番ノイズが少ない通信路を盗聴者が用いるものとして安全性を確保する必要がある.そのため,通信路を比較するための順序を導入する必要があり,これまでもless noisy order (Korner-Marton, 1975) など,通信路に関する様々な順序が研究されてきた.中でも,二つの通信路W, V が与えられたとき,一方の通信路V が他方の通信路Wにさらにノイズを付加した通信路となる関係W > V (degraded order) は統計的にも重要である(Blackwell-Sherman-Stein, 1951). 本論文では,通信路のノイズに関する順序(degraded order) について二つ観点で数値的な研究を行った.一つは通信路の順序と情報量(相互情報量および相対レニーエントロピー)の関係についての研究であり,もう一つは,順序を判定する効率的なアルゴリズムの開発である. 最初に,通信路の順序と相互情報量および相対レニーエントロピーの関係について数値実験による研究を行った.通信路W と通信路の入力アルファベット上の確率分布P が与えられると,相互情報量I(P;W) が計算できる.相互情報量の単調性(データ処理不等式)より,二つの通信路W, V が順序関係W > V を満たす(V はW よりノイズが多い)ならば,すべての入力分布Pについて,相互情報量の大小関係I(P;W) >_ I(P; V ) が成り立つ.本研究では,この命題の逆が成立するかどうかを調べるため,数値実験により,3 入力3 出力の通信路を多数調べることで反例を探した.その結果,反例として,非常に多くの入力分布P について,相互情報量の大小関係I(P;W) >_ I(P; V ) が成り立つが,順序関係W > V を満たさない例を多数見つけた.相対レニーエントロピーについても同様の単調性が成り立つことが知られている.この場合も同様に,単調性の逆の命題が成立しない多数の反例を見つけた. 次に,二つの通信路W, V が任意に与えられたとき,順序関係W > V が満たされるかどうかを判定する一般的なアルゴリズムの開発を行った.本論文では,通信路W に付加的なノイズU が加わる状況を考え,U を変えて行くことでW とU の合成通信路が通信路V に一致するかどうかを最急降下法により調べた.その際,コスト関数として確率遷移行列の成分の二乗和を用いた.また,付加するノイズU も確率遷移行列である必要がるため,U の行列成分は非負かつ行和は1 でなければならない.本論文では,U を指数分布族により表現することで,確率遷移行列の制約条件を満たしながらコスト関数を最小化するアルゴリズムを開発した.
量子コンピュータの実用的計算への応用を目指して、様々な量子アルゴリズムが提案されている。しかしながら現在の不完全な量子コンピュータ上では、従来提案されてきた量子アルゴリズムの実行が困難である場合が多く、より効率的な量子アルゴリズムの発見が求められている。そこで我々は、人工知能に量子計算の大量のデータを学習させることによって、量子アルゴリズムを学習させた。構築した人工知能は、少ないデータから量子計算の規則性を見出し、未知の入力に対しても正しい量子計算手順を出力できることが明らかになった。これは、開発した人工知能が少数のデータに内在する規則性を量子アルゴリズムとして理解し、未知のデータに対しても応用しているということを示している。