# (参考訳) 重み付きグラフ学習のための等価量子回路 [全文訳有]

Equivariant quantum circuits for learning on weighted graphs ( http://arxiv.org/abs/2205.06109v1 )

ライセンス: CC BY 4.0
Andrea Skolik, Michele Cattelan, Sheir Yarkoni, Thomas B\"ack, Vedran Dunjko(参考訳) 変分量子アルゴリズムは、雑音量子ハードウェアにおける短期的優位性の主要な候補である。 パラメータ化された量子回路をトレーニングして特定のタスクを解く場合、アルゴリズムのトレーニング可能性と性能を決定する最も重要な要素の1つである。 問題調整アンサーゼは最適化や量子化学のタスクの標準となり、非構造的アプローチよりも優れた性能を持つアルゴリズムを生み出している。 しかし、量子機械学習(qml)では、トレーニングデータ構造によって動機づけられたアンサtzeに関する文献は少ない。 システムサイズと回路深度を増大させることで非構造的アンサーゼがトレーニング不能になることが広く知られていることから、QMLコンテキストにおける問題調整回路アーキテクチャの研究も重要である。 本稿では,重み付きグラフのタスクを学習するためのアンサッツについて紹介する。 重み付きグラフ上の複素学習タスクにおけるこのアンサッツの性能を評価し,組合せ最適化問題に対するヒューリスティックを実装するためにmlモデルを用いた。 深さ1で ansatz の表現率を解析的に検討し,20 キュービットまでのインスタンスにおけるモデルの性能を,分散特性が徐々に破られる ansatzes と比較した。 当社のansatzは,小規模体制においても他国よりも優れています。 この結果から, 対称性保存アンサツェがQMLの成功の鍵であり, この分野での短期的優位性を実現するために研究の活発な領域であることが示唆された。

Variational quantum algorithms are the leading candidate for near-term advantage on noisy quantum hardware. When training a parametrized quantum circuit to solve a specific task, the choice of ansatz is one of the most important factors that determines the trainability and performance of the algorithm. Problem-tailored ansatzes have become the standard for tasks in optimization or quantum chemistry, and yield more efficient algorithms with better performance than unstructured approaches. In quantum machine learning (QML), however, the literature on ansatzes that are motivated by the training data structure is scarce. Considering that it is widely known that unstructured ansatzes can become untrainable with increasing system size and circuit depth, it is of key importance to also study problem-tailored circuit architectures in a QML context. In this work, we introduce an ansatz for learning tasks on weighted graphs that respects an important graph symmetry, namely equivariance under node permutations. We evaluate the performance of this ansatz on a complex learning task on weighted graphs, where a ML model is used to implement a heuristic for a combinatorial optimization problem. We analytically study the expressivity of our ansatz at depth one, and numerically compare the performance of our model on instances with up to 20 qubits to ansatzes where the equivariance property is gradually broken. We show that our ansatz outperforms all others even in the small-instance regime. Our results strengthen the notion that symmetry-preserving ansatzes are a key to success in QML and should be an active area of research in order to enable near-term advantages in this field.
公開日: Thu, 12 May 2022 14:15:47 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。


    Page: /      
Equivariant quantum circuits for learning on weighted graphs 重み付きグラフ学習のための等価量子回路 0.81
Andrea Skolik,1, 2 Michele Cattelan,2 Sheir Yarkoni,1, 2 Thomas B¨ack,1 and Vedran Dunjko1 Andrea Skolik,1,2 Michele Cattelan,2 Sheir Yarkoni,1,2 Thomas B sack,1 and Vedran Dunjko1 0.34
1Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands 1leiden university, niels bohrweg 1, 2333 ca leiden, オランダ 0.66
2Volkswagen Data:Lab, Ungererstraße 69, 80805 Munich, Germany 2Volkswagen Data:Lab, Ungererstraße 69, 80805ミュンヘン 0.71
(Dated: May 13, 2022) (2022年5月13日廃止) 0.50
Variational quantum algorithms are the leading candidate for near-term advantage on noisy quantum hardware. 変分量子アルゴリズムは、雑音量子ハードウェアにおける短期的優位性の主要な候補である。 0.70
When training a parametrized quantum circuit to solve a specific task, the choice of ansatz is one of the most important factors that determines the trainability and performance of the algorithm. パラメータ化された量子回路をトレーニングして特定のタスクを解く場合、アルゴリズムのトレーニング可能性と性能を決定する最も重要な要素の1つである。 0.80
Problem-tailored ansatzes have become the standard for tasks in optimization or quantum chemistry, and yield more efficient algorithms with better performance than unstructured approaches. 問題調整アンサーゼは最適化や量子化学のタスクの標準となり、非構造的アプローチよりも優れた性能を持つアルゴリズムを生み出している。 0.74
In quantum machine learning (QML), however, the literature on ansatzes that are motivated by the training data structure is scarce. しかし、量子機械学習(qml)では、トレーニングデータ構造によって動機づけられたアンサtzeに関する文献は少ない。 0.71
Considering that it is widely known that unstructured ansatzes can become untrainable with increasing system size and circuit depth, it is of key importance to also study problem-tailored circuit architectures in a QML context. システムサイズと回路深度を増大させることで非構造的アンサーゼがトレーニング不能になることが広く知られていることから、QMLコンテキストにおける問題調整回路アーキテクチャの研究も重要である。 0.81
In this work, we introduce an ansatz for learning tasks on weighted graphs that respects an important graph symmetry, namely equivariance under node permutations. 本稿では,重み付きグラフのタスクを学習するためのアンサッツについて紹介する。
訳抜け防止モード: 本稿では,アンザッツについて紹介する。 重要なグラフ対称性を尊重する重み付きグラフ上のタスクの学習。
We evaluate the performance of this ansatz on a complex learning task on weighted graphs, where a ML model is used to implement a heuristic for a combinatorial optimization problem. 重み付きグラフ上の複素学習タスクにおけるこのアンサッツの性能を評価し,組合せ最適化問題に対するヒューリスティックを実装するためにmlモデルを用いた。 0.78
We analytically study the expressivity of our ansatz at depth one, and numerically compare the performance of our model on instances with up to 20 qubits to ansatzes where the equivariance property is gradually broken. 深さ1で ansatz の表現率を解析的に検討し,20 キュービットまでのインスタンスにおけるモデルの性能を,分散特性が徐々に破られる ansatzes と比較した。 0.71
We show that our ansatz outperforms all others even in the small-instance regime. 当社のansatzは,小規模体制においても他国よりも優れています。 0.43
Our results strengthen the notion that symmetry-preserving ansatzes are a key to success in QML and should be an active area of research in order to enable near-term advantages in this field. この結果から, 対称性保存アンサツェがQMLの成功の鍵であり, この分野での短期的優位性を実現するために研究の活発な領域であることが示唆された。 0.65
I. INTRODUCTION Combinatorial optimization problems are ubiquitous, be it in transportation and logistics, electronics, or scheduling tasks. 私は... 導入 組合せ最適化問題は、輸送や物流、電子機器、スケジュールタスクなど、ユビキタスな問題である。 0.49
These types of problems have also been studied in computer science and mathematics for decades. この種の問題はコンピュータ科学や数学でも何十年も研究されてきた。 0.70
Many interesting combinatorial optimization problems that are relevant in industry today are NP-hard, so that no general efficient solution is expected to exist. 今日業界で関係している多くの興味深い組合せ最適化問題はNPハードであり、一般的な効率的な解は存在しない。 0.67
For this reason, heuristics have gained much popularity, as they often provide high-quality solutions to real-world instances of many NP-hard problems. このため、ヒューリスティックスはNPハード問題の多い現実世界のインスタンスに高品質なソリューションを提供することが多いため、多くの人気を得た。 0.59
However, good heuristics require domain expertise in their design and they have to be defined on a per-problem basis. しかし、優れたヒューリスティックスは設計にドメインの専門知識を必要とし、プロブレムごとに定義する必要がある。
訳抜け防止モード: しかし、優れたヒューリスティックは設計にドメインの専門知識を必要とする それらは問題ごとに定義する必要があります。
To circumvent handcrafting heuristic algorithms, machine learning approaches for solving combinatorial optimization problems have been studied. 手作りヒューリスティックアルゴリズムを回避するため、組合せ最適化問題を解決する機械学習アプローチが研究されている。 0.66
One line of research in this area investigates using neural networks (NNs) to learn algorithms for solving combinatorial optimization problems [1, 2], which is known as neural combinatorial optimization (NCO). この領域における研究の1行は、ニューラルネットワーク(NN)を用いて組合せ最適化問題 [1, 2] を解決するアルゴリズムを学習することである。
訳抜け防止モード: この領域における研究の1行は、組合せ最適化問題の解法を学ぶアルゴリズムをニューラルネットワーク(NN)を用いて研究している[1]。 2 ] NCO(Neural combinatorial Optimization)とも呼ばれる。
Here, NNs learn to solve combinatorial optimization problems based on data, and can then be used to find approximate solutions to arbitrary instances of the same problem. ここでは、NNはデータに基づく組合せ最適化問題の解法を学び、同じ問題の任意のインスタンスに対する近似解を見つけるために使用できる。 0.82
First approaches in this direction used supervised learning to find approximate solutions based on NN techniques from natural language processing [3]. この方向の最初のアプローチは、自然言語処理からのNN技術に基づく近似解を見つけるために教師あり学習を用いた[3]。 0.77
A downside of the supervised approach is that it requires access to a large amount of training data in form of solved instances of the given problem, which requires solving many NP-hard instances of the problem to completion. 教師付きアプローチの欠点は、与えられた問題の解決されたインスタンスの形で大量のトレーニングデータにアクセスする必要があることである。
訳抜け防止モード: 教師付きアプローチの欠点は、与えられた問題の解決されたインスタンスの形で大量のトレーニングデータにアクセスする必要があることである。 多くのNPを解決しなければなりません。
At large problem sizes, this is a serious impediment for the practicability of this method. 大きな問題の規模では、この方法の実用性に深刻な障害があります。 0.74
For this reason, reinforcement learning (RL) was introduced as a technique to train these heuristics. そのため、これらのヒューリスティックスを訓練する手法として強化学習(RL)を導入した。 0.72
In RL, an agent does not learn based on a given data set, but by rlでは、エージェントは与えられたデータセットに基づいて学習するのではなく、 0.76
interacting with an environment and gathering information in a trial-and-error fashion. 環境と対話し、試行錯誤の方法で情報を集める。 0.69
These RL-based approaches have been shown to successfully solve even instances of significant size in problems with a geometric structure like the convex hull problem [4], chip placement [5] or the vehicle routing problem [6]. これらのRLに基づくアプローチは, 凸船体問題[4], チップ配置[5], 車両経路問題[6]のような幾何学的構造を持つ問題において, かなりの大きさの問題を解くことに成功している。 0.81
In most combinatorial optimization problems the instances are presented in a structured form, for instance as a graph, so the structure of the ML models underlying the above techniques can be chosen in an informed manner. ほとんどの組合せ最適化問題において、インスタンスは、例えばグラフとして構造化形式で表現されるので、上記の手法の基盤となるMLモデルの構造は、情報的な方法で選択することができる。 0.69
In recent years the field that focuses on the study of exploiting this known structure, called geometric deep learning, has garnered a lot of interest [7]. 近年、幾何学的深層学習と呼ばれるこの既知の構造を利用する研究に焦点をあてた分野が、多くの関心を集めている [7]。 0.80
This field studies the properties of common NN architectures, like convolutional NNs or graph NNs, through the lens of group theory and geometry and provides an understanding of why these structured types of models are the main drivers of recent advances in deep learning. この分野は、グループ理論と幾何学のレンズを通して、畳み込みNNやグラフNNのような共通のNNアーキテクチャの特性を研究し、これらの構造されたモデルが、最近のディープラーニングの進歩の主要因である理由を理解する。 0.71
The success of these models can largely be attributed to the fact that they preserve certain symmetries that are present in the training data, e g , translation invariance in images in the case of convolutional NNs, or permutation invariance or equivariance in the case of graph NNs, as depicted in fig. これらのモデルの成功は、例えば、畳み込みNNの場合の画像の変換不変性、あるいはグラフNNの場合の置換不変性や同値性など、トレーニングデータに存在する特定の対称性を保存しているという事実が主な原因である。 0.67
1. When it comes to quantum computing, much work has been dedicated to understanding the structure for variational quantum algorithms [8] that address problems in optimization [9, 10] or chemistry [11, 12]. 1. 量子コンピューティングに関しては、最適化 [9, 10] や化学 [11, 12] の問題に対処する変分量子アルゴリズム [8] の構造を理解することに多くの研究が費やされている。 0.65
For quantum machine learning however, it is largely unknown which type of ansatz should be used for a given type of data. しかし、量子機械学習では、特定の種類のデータに対してどの種類のアンサッツを使用するべきかはほとんど分かっていない。 0.55
In absence of an informed choice, general architectures as the hardware efficient ansatz (HWEA) [13] are often used [14]. 情報選択がなければ、ハードウェア効率の良いアンサッツ(HWEA)[13]として一般的なアーキテクチャがよく使用される[14]。 0.80
It is known that unstructured ansatzes like the HWEA scale badly as the width and depth of the circuit grows, most prominently because of the barren plateau phenomenon [15– 回路の幅と深さが大きくなるにつれて、hweaのような非構造的なアンサtzeがひどくなり、特に不毛高原現象が顕著である [15-]。 0.67
2 2 0 2 y a M 2 1 2 2 0 2 y a m 2 1 である。 0.52
] h pt n a u q [ ] h pt n a u q [ 0.42
1 v 9 0 1 6 0 1 v 9 0 1 6 0 0.43
. 5 0 2 2 : v i X r a . 5 0 2 2 : v i X r a 0.42
17] where the gradients of a parametrized quantum circuit (PQC) vanish exponentially as the system size grows and thus render training impossible. 17] システムサイズが大きくなるとパラメトリック量子回路(PQC)の勾配が指数関数的に消失し、トレーニングが不可能になる。 0.81
This situation can be compared to the early days of NNs, where fully connected feedforward NNs were the standard architecture. この状況は、完全に接続されたフィードフォワードNNが標準アーキテクチャであったNNの初期と比べることができる。 0.64
These types of NNs suffer from similar trainability issues as unstructured quantum circuits [18]. これらのタイプのnnは、非構造化量子回路[18]と同様のトレーサビリティの問題に苦しむ。 0.62
The true break-throughs in deep learning were in part possible because more efficient architectures have been developed, like the convolutional NN for image recognition or the recurrent NN for time series. 深層学習における真のブレークスルーは、画像認識のための畳み込みNNや時系列のための繰り返しNNのような、より効率的なアーキテクチャが開発されたためである。 0.63
In this work, we introduce a permutation equivariant quantum circuit architecture for weighted graphs and demonstrate that it significantly outperforms unstructured ansatzes. 本研究では、重み付きグラフに対する置換同変量子回路アーキテクチャを導入し、非構造的アンサーゼを著しく上回ることを示す。 0.66
To evaluate these ansatzes on a complex learning task that is relevant for solving industry-related problems once scaled up in instance size, we study their performance in the context of neural combinatorial optimization to find approximate solutions to the Traveling Salesperson Problem (TSP). 事例のサイズを拡大した産業関連問題の解決に関係した複雑な学習課題に対するこれらの不満を評価するために, ニューラルネットワーク最適化の文脈でそれらの性能を調査し, トラベリングセールスパーソン問題(TSP)の近似解を求める。 0.77
Our contributions are as follows. 私たちの貢献は以下の通りです。 0.61
• We introduce an equivariant ansatz for learning • 学習のための同変 ansatz を導入する 0.70
on weighted graphs. • We evaluate the performance of this ansatz on the task of solving TSP instances and show that it performs well on instances with up to 20 cities (20 qubits). 重み付きグラフです • 最大20都市 (20 qubits) のインスタンスにおいて, TSP インスタンスの解決作業において, このアンザッツの性能を評価し, 性能が良好であることを示す。 0.68
• We numerically compare our ansatz to three non-equivariant ansatzes, and show that the more the equivariance property of the ansatz is broken, the worse performance becomes and that a simple hardware-efficient ansatz completely fails on this learning task. • ansatz と 3 つの非等価な ansatze を数値的に比較し、ansatz の等分散性が破られるほど、パフォーマンスが悪化し、単純なハードウェア効率の ansatz がこの学習タスクで完全に失敗することを示した。 0.78
• We analytically study the expressivity of our model at depth one, and show under which conditions there exists a parameter setting for any given TSP instance of arbitrary size for our ansatz that produces the optimal tour with the RL scheme that is applied in this work. • 深さ1でモデルの表現率を解析的に検討し、本研究で適用されるrlスキームを用いて最適なツアーを生成する ansatz の任意の大きさの任意の tsp インスタンスに対するパラメータ設定が存在するかを示す。 0.76
Our work illustrates the merit of using symmetrypreserving ansatzes for QML on the example of graphbased learning, and underlines the notion that in order to successfully apply variational quantum algorithms for ML tasks in the future, the usage of unstructured ansatzes that are popular in current QML research is limited as problem sizes grow. 本研究は、グラフベース学習の例において、QMLの対称性保存アンサーゼを使用することのメリットを示し、将来、MLタスクに変分量子アルゴリズムをうまく適用するために、現在のQML研究で広く使われている非構造的アンサーゼの使用は、問題のサイズが大きくなるにつれて制限される、という概念を下記している。
訳抜け防止モード: 私たちの作品には、そのメリットが示されています グラフベースの学習の例におけるQMLの対称性保存アンサーゼの使用 そしてその考え方は 未来のMLタスクに変分量子アルゴリズムをうまく適用するために 現在のQML研究で人気がある非構造化アンサーゼの使用は、問題のサイズが大きくなるにつれて制限される。
This work motivates further study of “geometric quantum learning” in the vein of the classical field of geometric deep learning, to establish more effective ansatzes for QML, as these are a prerequisite to efficiently apply quantum models on any practically relevant learning task in the near-term. この研究は、幾何学的深層学習の古典的な分野における「幾何学的量子学習」のさらなる研究を動機付け、QMLのより効果的なアンサーゼを確立する。
訳抜け防止モード: この研究は、幾何学的深層学習の古典的な分野の静脈における「幾何学量子学習」のさらなる研究を動機付けている。 前提条件であるQMLのためのより効果的なアンサーゼを確立する 近い将来、実用的な学習タスクに量子モデルを効果的に適用する。
The full code that was used to generate the numerical results in this work can be found on GitHub [19]. この作業で数値結果を生成するために使用された完全なコードはGitHub [19]で見ることができる。 0.82
2 FIG. 1: Depiction of two functions that respect important symmetries of graphs: 2 FIG. 1: グラフの重要な対称性を尊重する2つの関数の解釈 0.63
a) The permutation equivariant function will yield the same output values for each graph permutation, but reordered according to the reordering of nodes. a) 置換同変関数は各グラフの置換に対して同じ出力値を与えるが、ノードの再順序付けに従って再順序付けされる。 0.72
The above example shows a simple function that outputs node features in the same order as they are fed into the function. 上記の例は、関数に入力されたノードの特徴を同じ順序で出力する単純な関数を示している。 0.87
b) An invariant function will yield the same output, regardless of the permutation. b) 不変関数は、置換にかかわらず、同じ出力を生成する。 0.67
The above example shows a simple function that outputs node features in ascending order. 上記の例では、ノードの特徴を昇順に出力する単純な関数を示している。 0.72
Which of the two is preferable depends on the task at hand. 2つのうちどちらが望ましいかは、目の前の作業次第です。 0.58
II. RELATED WORK A. Geometric learning - quantum and classical II。 関連作業 A.幾何学学習-量子と古典 0.73
Learning approaches that utilize geometric properties of a given problem have lead to major successes in the field of ML, such as AlphaFold for the complex task of protein folding [20, 21] and have become an increasingly popular research field over the past few years. 与えられた問題の幾何学的性質を利用する学習アプローチは、タンパク質の折り畳み(20,21)の複雑なタスクにおけるAlphaFoldのようなMLの分野で大きな成功をもたらし、ここ数年でますます人気のある研究分野となった。 0.86
Arguably the prime example of a successful geometric model is the convolutional NN (CNN), which has been developed at the end of the 20th century in an effort to enable efficient training of image recognition models [22]. 20世紀末に画像認識モデルの効率的なトレーニングを可能にするために開発されたconvolutional nn (cnn) が成功した。
訳抜け防止モード: おそらく、成功した幾何学モデルの主要な例は畳み込みNN(CNN)である。 20世紀末に開発されました 画像認識モデルの効率的な訓練を可能にする[22]。
Since then, it has been shown that one of the main reasons that CNNs are so effective is that they are translation invariant: if an object in a given input image is shifted by some amount, the model will still “recognize” it as the same object and thus effectively requires fewer training data [7]. それ以来、cnnがとても効果的である主な理由の1つは、それらが翻訳不変であるということである: ある入力画像内のオブジェクトが何らかの量でシフトされたとしても、モデルはまだ同じオブジェクトとしてそれを“認識”し、より少ないトレーニングデータを必要とする [7]。 0.79
While CNNs are the standard architecture used for images, symmetry-preserving architectures have also been developed for time-series data in the form of recurrent NNs [23], and for graph data with GNNs [24]. cnnは画像に使用される標準的なアーキテクチャであるが、対称性保存アーキテクチャはリカレントnn [23] という形式で時系列データやgnn [24] を使用したグラフデータに対しても開発されている。
訳抜け防止モード: CNNはイメージに使用される標準的なアーキテクチャである。 対称性 - 保存アーキテクチャも長い間開発されてきた - 繰り返しNNの形式での時系列データ[23]。 そして、GNNによるグラフデータ [24 ]。
GNNs have seen a surge of interest in the classical machine learning community in the past decade [24, 25]. GNNは、過去10年間に古典的な機械学習コミュニティへの関心が高まってきた[24, 25]。 0.71
They are designed to process data that is presented in graph form, like social networks [24], molecules [26], images [27] or instances of combinatorial optimization problems [1]. それらは、ソーシャルネットワーク[24]、分子[26]、画像[27]、組合せ最適化問題のインスタンス[1]などのグラフ形式で表示されるデータを処理するように設計されています。
訳抜け防止モード: グラフ形式で表示されるデータを処理するように設計されている。 ソーシャルネットワーク[24] 分子[26] のように image [ 27 ] または組合せ最適化問題のインスタンス [ 1 ]
The first attempt to implement a geometric learning model in the quantum realm was made with the quantum convolutional NN in [28], where the authors introduce a translation invariant architecture motivated by classical convolutional NNs. 量子領域で幾何学的学習モデルを実装する最初の試みは[28]の量子畳み込みnnを用いて行われ、著者らは古典畳み込みnnに動機づけられた翻訳不変量構造を導入した。 0.70
Approaches to translate the GNN formalism to QNNs were taken in [29], where input graphs are represented in terms of a parametrized Hamiltonian, which is then used GNN形式をQNNに翻訳するアプローチは[29]で行われ、入力グラフはパラメトリケートされたハミルトニアンで表現され、その後使われる。 0.71
permutation (a) equivariant function 置換 (a)同変関数 0.65
(b) invariant function 51243555551111133333 2222244444 (b)不変関数51243555551113333322 4444 0.37
to prepare the ansatz of a quantum model called a quantum graph neural network (QGNN). 量子グラフニューラルネットワーク(QGNN)と呼ばれる量子モデルのアンサッツを作成する。 0.70
While the approach in [29] yields promising results, this work does not take symmetries of the input graph into account. この[29]のアプローチは有望な結果をもたらすが、この研究は入力グラフの対称性を考慮に入れていない。 0.73
The authors of [30] introduce the so-called quantum evolution kernel, where they devise a graphbased kernel for a quantum kernel method for graph classification. 30]の著者らは、いわゆる量子進化カーネルを導入し、グラフ分類のための量子カーネル法のためのグラフベースのカーネルを考案した。 0.76
Again, their ansatz is based on alternating layers of Hamiltonians, where one Hamiltonian in each layer encodes the problem graph, while a second parametrized Hamiltonian is trained to solve a given problem. 繰り返しになるが、それらのアンザッツはハミルトン多様体の交互層に基づいており、各層に1つのハミルトニアンが問題のグラフをエンコードし、2番目のパラメタ化ハミルトニアンが与えられた問題を解くために訓練される。
訳抜け防止モード: 再び、彼らのアンサッツはハミルトン人の交互層に基づいている。 各層のハミルトニアンが問題グラフをエンコードし 第2のパラメータ化ハミルトンは 与えられた問題を解決するために訓練されています
A proposal for a quantum graph convolutional NN was made in [31], and the authors of [32] propose directly encoding the adjacency matrix of a graph into a unitary to build a quantum circuit for graph convolutions. 量子グラフ畳み込みnnの提案は[31]で行われ、[32]の著者はグラフの隣接行列を直接ユニタリに符号化して、グラフ畳み込みのための量子回路を構築することを提案している。 0.81
While all of the above works introduce forms of structured QML models, none of them study their properties explicitly from a geometric learning perspective or relate their performance to unstructured ansatzes. 上記の全ての研究は構造化QMLモデルを導入しているが、幾何学的学習の観点からその特性を明示的に研究したり、その性能を非構造化のアンサーゼに関連づけたりはしない。
訳抜け防止モード: 上記の研究はすべて構造化QMLモデルを導入している。 幾何学的学習の観点から 明確に研究する者はいません あるいはそのパフォーマンスを アンサーゼに関連付けます
The authors of [33] take the step to introduce an equivariant model family for graph data and generalize the QGNN picture to so-called equivariant quantum graph circuits (EQGCs). 筆者ら[33]は、グラフデータのための同変モデルファミリーを導入し、QGNN画像をいわゆる同変量子グラフ回路(EQGC)に一般化する。 0.69
EQGCs are a very broad class of ansatzes that respect the connectivity of a given input graph. EQGCは、与えられた入力グラフの接続性を尊重する非常に広いクラスである。 0.77
The authors of [33] also introduce a subclass of EQGCs called equivariant quantum Hamiltonian graph circuits (EH-QGCs), that includes the QGNNs by [29] as a special case. また[33]の著者は、[29]によるQGNNを含む等変量子ハミルトングラフ回路(EH-QGC)と呼ばれるEQGCのサブクラスも導入している。 0.80
EH-QGCs are implemented in terms of a Hamiltonian that is constructed based on the input graph structure, and they are explicitly equivariant under permutation of vertices in the input graph. EH-QGCは入力グラフ構造に基づいて構築されるハミルトニアンの項で実装され、入力グラフ内の頂点の置換の下で明示的に同変である。 0.79
The framework that the authors of [33] propose can be seen as a generalization of the above proposals. 33] の著者が提案した枠組みは、上記の提案の一般化と見なすことができる。 0.76
Different from the above proposals, EQGCs use a post-measurement classical layer that performs the functionality of an aggregation function as those found in classical GNNs. 上記の提案と異なり、EQGCは古典的なGNNで見られるような集約関数の機能を実行する後古典的なレイヤを使用する。 0.70
In classical GNNs, the aggregation function in each layer is responsible for aggregating node and edge information in an equivariant or invariant manner. 古典的なGNNでは、各層の集約関数は、同変または不変の方法でノードとエッジ情報を集約する。 0.71
Popular aggregation functions are sums or products, as they trivially fulfill the equivariance property. 一般的な集約関数は和や積であり、それらは同値性を自明に満たす。 0.55
In the case of EQGCs, there is no aggregation in the quantum circuit, and this step is offloaded to a classical layer that takes as input the measurements of the PQC. EQGC の場合、量子回路にアグリゲーションはなく、このステップは古典的な層にオフロードされ、PQC の測定が入力される。 0.64
Additionally, the EQGC family is defined over unweighted graphs and only considers the adjacency matrix of the underlying input graph to determine the connectivity of the qubits. さらに、EQGC族は、未重み付きグラフ上で定義され、基礎となる入力グラフの隣接行列のみを考慮し、量子ビットの接続性を決定する。 0.67
The authors of [33] also show that their EQGC outperforms a standard message passing neural network on a graph classification task, and thereby demonstrate a first separation of quantum and classical models on a graph-based learning task. また、[33]の著者らは、EQGCがグラフ分類タスクにおいて標準的なメッセージパッシングニューラルネットワークより優れており、グラフベースの学習タスクにおいて量子モデルと古典モデルの最初の分離を示すことを示した。
訳抜け防止モード: また,[33 ] の著者らは,EQGC が標準メッセージパッシングニューラルネットワークをグラフ分類タスクで上回ることを示した。 これにより、グラフベースの学習タスクで量子モデルと古典モデルの最初の分離を示す。
During preparation of our final manuscript, a work on invariant quantum machine learning models was released by the authors of [34]. 最終稿の準備中に,[34]の著者らによって不変量子機械学習モデルの研究が発表された。 0.77
They prove for a number of selected learning tasks whether an invariant quantum machine learning model for specific types of symmetries exists. 彼らは、特定の種類の対称性に対する不変量子機械学習モデルが存在するかどうか、いくつかの選択された学習タスクを証明する。
訳抜け防止モード: 選択された学習タスクが 特定の種類の対称性に対する不変量子機械学習モデルが存在する。
Their work focuses on group invariance, and leaves proposals for NISQ-friendly equivariant quantum models as an open question. 彼らの研究は群不変性に焦点を当て、オープンな問題として NISQ に優しい同変量子モデルの提案を残している。 0.53
3 Our proposal is most closely related to EH-QGCs, but with a number of deviations. 3 提案手法はEH-QGCと密接な関係があるが,多くの相違点がある。 0.49
First, our model is defined on weighted graphs and can therefore be used for learning tasks that contain node as well as edge features. まず、このモデルは重み付きグラフに基づいて定義されており、ノードやエッジ機能を含むタスクの学習に使用することができる。 0.73
Second, the initial state of our model is always the uniform superposition, which allows each layer in the ansatz to perform graph feature aggregation via sums and products of node and edge features, as we will discuss in section III. 第2に、我々のモデルの初期状態は常に一様重ね合わせであり、第3節で論じるように、アンザッツの各層はノードとエッジの積の和と積を通じてグラフ特徴集計を行うことができる。 0.75
Third, we do not require a classical post-processing layer, so our EQC model is purely quantum. 第三に、我々は古典的な後処理層を必要としないので、EQCモデルは純粋に量子的である。
訳抜け防止モード: 第三に、古典的なポスト-処理層は不要です。 私たちのEQCモデルは純粋に量子的です。
Additionally, in its simplest form as used in this work, the number of qubits in our model scales linearly with the number of nodes in the input graph, while the depth of each layer depends on the graph’s connectivity, and therefore it provides one answer to the question of a NISQ-friendly equivariant quantum model posed by [34]. さらに、この研究で使用される最も単純な形式では、我々のモデルの量子ビットの数は入力グラフのノードの数と線形にスケールするが、各層の深さはグラフの接続性に依存するため、[34] で表される NISQ フレンドリな同変量子モデルの問題に対する1つの答えとなる。 0.85
B. Neural combinatorial optimization with B.ニューラル組合せ最適化 0.81
reinforcement learning The idea behind NCO is to use a ML model to learn a heuristic for a given optimization problem based on data. 強化学習 NCOの背景にある考え方は、データに基づいて与えられた最適化問題のヒューリスティックを学ぶために、MLモデルを使用することである。
訳抜け防止モード: 強化学習 NCOの背景にあるアイデアは MLモデルを使用して、データに基づいた最適化問題に対するヒューリスティックを学習する。
When combined with RL, this data manifests in form of states of an environment, while the objective is defined in terms of a reward function, as we will now explain in more detail. RLと組み合わせると、このデータは環境の状態の形で表され、目的は報酬関数の観点で定義される。
訳抜け防止モード: RLと組み合わせると、このデータは環境の状態の形で表される。 目的は報酬関数の観点で定義されますが、今より詳しく説明します。
In the RL paradigm, the model, referred to as an agent, interacts with a socalled environment. RLパラダイムでは、エージェントと呼ばれるモデルがいわゆる環境と相互作用する。 0.56
The environment is defined in terms of its state space S and action space A, that can both either be discrete or continuous. 環境は状態空間 s と作用空間 a によって定義され、離散的でも連続的でも構わない。 0.76
The agent alters the state of the environment by performing an action a ∈ A, whereafter it receives feedback from the environment in form of the following state s(cid:48) ∈ S, and a reward r that depends on the quality of the chosen action, given the initial state s. エージェントは、動作 a ∈ A を実行して環境の状態を変更し、その後、以下の状態 s(cid:48) ∈ S の形で環境からフィードバックを受け、初期状態 s が与えられた場合、選択された動作の品質に依存する報酬 r を与えられる。 0.78
Actions are chosen based on a policy π(a|s), which is a probability distribution of actions a given states s. アクションは、与えられた状態 s に対するアクションの確率分布であるポリシー π(a|s) に基づいて選択される。 0.81
The definition of the state and action spaces and the reward function depends on the given environment. 状態とアクション空間の定義と報酬関数は、与えられた環境に依存する。 0.72
In general, the goal of the agent is to learn a policy that maximizes the expected return G, 一般に、エージェントの目標は、期待される戻り値Gを最大化するポリシーを学ぶことである。 0.78
∞(cid:88) Gt = ∞(cid:88) Gt = 0.42
γkrt+k+1, γkrt+k+1 である。 0.32
(1) k=0 where γ ∈ [0, 1] is the discount factor that determines the importance of future rewards in the agent’s decision. (1) K=0 ここで γ ∈ [0, 1] はエージェントの決定における将来の報酬の重要性を決定する割引係数である。 0.51
The above definition of the expected return is for the so-called infinite horizon, where the interaction with the environment can theoretically go on to infinity. 以上の定義は、環境との相互作用が理論上無限大へと続くようないわゆる無限地平線に対するものである。 0.68
In practice. we usually work in environments with a finite horizon, where the above sum runs only over a predefined number of indices. 実際には。 通常は有限の地平線を持つ環境で働きます 上記の和は 予め定義された数の指標でしか実行できません
訳抜け防止モード: 実際には。 通常 地平線が有限な環境で 上記の和は、予め定義されたインデックスの個数でのみ実行される。
There are many different approaches to maximize the expected return, and we refer the interested reader to [35] for an in-depth introduction. 期待するリターンを最大化するためのアプローチは数多くあり、詳細な紹介には興味のある読者を [35] に紹介する。 0.71
In this work, we focus on so-called Q-learning, where the expected return is maximized in terms of Q-values. 本研究では,q値の観点で期待値が最大化されるいわゆるq-learningに注目した。 0.72
The values Q(s, a) for each (s, a) pair also 各(s, a)ペアの値 Q(s, a) も 0.71
4 FIG. 2: An illustration of one episode in the TSP environment. 4 FIG.2:TSP環境における一つのエピソードのイラスト。 0.63
The agent receives a graph instance as input, where the first node is already added to the proposed tour (marked red), which can always be done without loss of generality. エージェントはグラフインスタンスを入力として受け取り、最初のノードが提案されたツアーに既に追加されている(赤にマークされている)。
訳抜け防止モード: エージェントはグラフインスタンスを入力として受け取り、最初のノードが提案されたツアーに既に追加されている(マークレッド)。 一般性を失わずに できることです
In each time step, the agent proposes which node should be added to the tour next. 各タイムステップで、エージェントは、次のツアーに追加すべきノードを提案する。 0.63
After the second-to-last node has been selected, the agent returns a proposed tour. 2番目のノードが選択されると、エージェントは提案されたツアーを返す。 0.60
represent the expected return following a policy π, but now conditioned on an initial state st and action at, 方針 π の後に期待値を返すが、初期状態 st で条件付けされ、アクション at, 0.68
Q(s, a) = Eπ[Gt|s = st, a = at]. q(s, a) = eπ[gt|s = st, a = at] である。 0.80
(2) When the agent is implemented in form of a NN, the goal of the NN is to approximate the optimal Qfunction Q∗. (2) エージェントがNN形式で実装されると、NNの目標は最適なQ関数 Q∗ を近似することである。 0.55
One popular method to use a NN as a function approximator for Q-learning is called the deep Q-network (DQN), and the resulting DQN algorithm [36]. NNをQラーニングの関数近似器として使用する一般的な方法は、ディープQネットワーク(DQN)と呼ばれ、結果として得られるDQNアルゴリズム[36]である。 0.74
In this algorithm, the NN is trained similarly as in the supervised case, but without a given set of labelled examples. このアルゴリズムでは、NNは教師付きケースと同様に訓練されるが、与えられたラベル付き例は含まない。 0.65
Instead, the agent collects samples at training time by interacting with the environment. その代わり、エージェントは環境と対話することでトレーニング時にサンプルを収集する。 0.70
These samples are stored in a memory, out of which a batch of random samples is drawn for each parameter update step. これらのサンプルはメモリに格納され、パラメータ更新ステップ毎にランダムなサンプルのバッチが描画される。 0.78
Based on the agent’s output, the label for a given (s, a) pair from the memory is computed as follows, エージェントの出力に基づいて、メモリから与えられた(s, a)ペアのラベルを次のように計算する。 0.70
q = rt+1 + γ · max q = rt+1 + γ · max 0.47
a ˆQθ(st+1, a), あ qθ(st+1, a) である。 0.55
(3) and this label is then used to compute parameter updates. (3) このラベルはパラメータの更新を計算するのに使われます 0.59
The update is not computed with the output of the function approximator Q, but by a copy ˆQ called the target network, which is updated with the current parameters of the function approximator at fixed intervals. この更新は関数近似器qの出力で計算されるのではなく、目標ネットワークと呼ばれるコピーqによって計算され、固定間隔で関数近似器の現在のパラメータで更新される。 0.76
The purpose of this target network is to stabilize training, and how often it is updated is a hyperparameter that depends on the environment. このターゲットネットワークの目的はトレーニングの安定化であり、その更新頻度は環境に依存するハイパーパラメータである。 0.72
In our case, the function approximator and target network are implemented as PQCs, while the parameter optimization is perfomed via the classical DQN algorithm. 院 我々の場合、関数近似器とターゲットネットワークはPQCとして実装され、パラメータ最適化は古典的なDQNアルゴリズムによって実現される。 0.59
For more detail on implementing the DQN algorithm with a PQC as the function approximator, we refer the reader to [37–39]. 関数近似器としてPQCを用いたDQNアルゴリズムの実装の詳細については、[37-39]を参照する。 0.82
1. Solving the Traveling Salesperson Problem with 1.旅行セールスパーソンの問題を解決する 0.76
reinforcement learning To evaluate the performance gains of an ansatz that respects certain symmetries relevant to the problem at hand, we apply our model to a practically motivated learning task on graphs. 強化学習 問題に関連する一定の対称性を尊重するansatzの性能向上を評価するために,本手法をグラフ上の実質的に動機づけられた学習タスクに適用する。 0.75
The TSP is a low-level abstraction of a problem commonly encountered in mobility and logistics: given a list of locations, find the shortest route that connects all of these locations without visiting any of them twice. TSPは、モビリティとロジスティクスで一般的に遭遇する問題の低レベルな抽象化である: 場所のリストが与えられたら、これらすべての場所を2度訪れずに接続する最も短いルートを見つける。 0.70
Formally, given a graph G(V,E) with vertices V and weighted edges E, the goal is to find a permutation of the vertices such that the resulting tour length is minimal, where a tour is a cycle that visits each vertex exactly once. 形式的には、頂点 V と重み付き辺 E を持つグラフ G(V,E) が与えられたとき、その目標は、ツアーの長さが最小となるような頂点の置換を見つけることである。
訳抜け防止モード: 形式的には、頂点 V と重み付き辺 E を持つグラフ G(V, E ) が与えられる。 ゴールは 頂点の順応を 見つけ出すことです ツアーの長さは最小限で ツアーはそれぞれの頂点を 正確に1度訪問するサイクルです
A special case of the TSP is the 2D Euclidean TSP, where each node is defined in terms of its x and y coordinates in Euclidean space, and the edge weights are given by the Euclidean distance between these points. TSP の特別なケースは 2D ユークリッド TSP であり、各ノードはユークリッド空間の x と y の座標で定義され、エッジウェイトはこれらの点間のユークリッド距離によって与えられる。 0.74
In this work, we deal with the symmetric Euclidean TSP on a complete graph, where the edges in the graph are undirected. この研究では、グラフの辺が無向である完全グラフ上の対称ユークリッド TSP を扱う。 0.56
This reduces the number of possible tours from n! to (n−1)! これにより、可能なツアーの数が n から (n−1)! 0.84
. However, even in this reduced case the number of possible tours is already larger than 100k for instances with a modest number of ten cities, . しかし、この縮小例でさえ、10都市という控えめな数のインスタンスでは、可能なツアーの数がすでに1万を超えている。 0.57
2 EQCstateactionagento ne episoden-2 timesinput: graphoutput: tour 2 EQCstateactionagento ne episoden-2 timesinput: graphoutput: Tour 0.45
and the TSP is a well-known NP-hard problem. TSPはよく知られたNPハード問題である。 0.73
To solve this problem with a RL approach, we follow the strategy introduced in [4]. この問題をRLアプローチで解決するには,[4]で導入された戦略に従う。 0.84
In this work, a classical GNN is used to solve a number of combinatorial optimization problems on graphs. この研究では、グラフ上の多くの組合せ最適化問題を解くために古典的なGNNが用いられる。 0.72
The authors show that this approach can outperform dedicated approximation algorithms defined for the TSP, like the Christofides algorithm, on instances of up to 300 cities. 著者らは、このアプローチが最大300都市の例で、クリストフィデスアルゴリズムのように、tspで定義された専用近似アルゴリズムを上回ることができることを示した。
訳抜け防止モード: 著者らは、この手法がTSPで定義された専用近似アルゴリズムより優れていることを示した。 クライストフィデスのアルゴリズムのように 最大300都市で
One episode of this learning algorithm for the TSP can be seen in fig. TSPのためのこの学習アルゴリズムの1つのエピソードは、フィグで見ることができる。 0.59
2, and a detailed description of the learning task as implemented in our work is given in section IV A. 第2節では,本研究で実施した学習タスクの詳細な説明が第4節aで述べられている。 0.61
In this section, we formally introduce the structure of our equivariant quantum circuit (EQC) for learning tasks on weighted graphs that we use in this work. 本稿では,本研究で用いた重み付きグラフ上のタスクを学習するための等変量子回路(EQC)の構造を正式に紹介する。 0.84
One well-known example of graph-based data are images, which are pixel values ordered on a 2Dgrid with nearest-neighbor connections. グラフベースのデータのよく知られた例は画像であり、2Dグリッド上に最寄りの接続を持つピクセル値である。 0.66
Other types of data that are represented in graph form are, for example, social networks or molecules. グラフ形式で表現される他の種類のデータは、例えばソーシャルネットワークや分子である。 0.78
In general, when learning based on graph data, there are two sets of features: node features and edge features. 一般的に、グラフデータに基づく学習には、ノード機能とエッジ機能という2つの機能セットがあります。 0.75
Depending on the specific learning task, it might be enough to use only one set of these features as input data, and the specific implementation of the circuit will change accordingly. 特定の学習タスクによっては、これらの機能のセットを入力データとして使用するだけで十分であり、それに従って回路の実装が変更される。 0.74
As mentioned above, an example of an ansatz for cases where encoding node features suffices is the EQGC introduced in [33]. 前述のように、ノードの特徴が十分である場合のアンサッツの例は[33]で導入されたEQGCである。 0.76
In our case, we use both node and edge features to solve TSP instances. 我々の場合、私たちはTSPインスタンスを解決するためにノード機能とエッジ機能の両方を使用します。 0.59
In case of the nodes, we encode whether a node is already present in the partial tour at time step t to inform the node selection process described later in definition 2. ノードの場合、時間ステップtにおける部分ツアーに既にノードが存在するかどうかを符号化し、後述するノード選択過程を後述する。 0.70
For the edges, we simply encode the edge weights of the graph as these correspond to the distance between nodes in the 2D Euclidean graph. エッジに対しては、2次元ユークリッドグラフのノード間の距離に対応するため、グラフのエッジ重みを単純に符号化する。 0.71
In this work, we use one qubit per node in the graph, but in general multiple qubits per node are also possible. この研究では、グラフに1ノード当たり1キュービットを使用するが、一般に1ノード当たりの複数のキュービットも可能である。
訳抜け防止モード: この作業では、グラフ内のノード毎に1キュービットを使用します。 一般にノード当たりの複数のキュービットも可能です
We discuss the details of this in appendix A. We now proceed to define the ansatz in terms of encoding node information in form of α (see definition 1) and edge information in terms of the weighted graph edges εij ∈ E. 我々は、ノード情報をαの形でエンコーディングする(定義1を参照)とともに、重み付きグラフ辺 εij ∈ e の観点でエッジ情報を定義する。 0.56
A. Ansatz structure and equivariance a.アンサッツ構造と等分散 0.64
Given a graph G(V,E) with node features α and weighted edges E, and trainable parameters β, γ ∈ Rp, our ansatz at depth p is of the following form ノードが α で重み付き辺 e と訓練可能なパラメータ β, γ ∈ rp を持つグラフ g(v,e) が与えられたとき、深さ p における我々のアンサッツは次の形式である。
訳抜け防止モード: ノードを持つグラフ G(V, E) が与えられたとき、α と重み付きエッジ E, トレーニング可能なパラメータ β , γ ∈ Rp , 深さ p のアンザッツは以下の形式です
|E, α, β, γ(cid:105)p = UN (α, βp)UG(E, γp) |E, α, β, γ(cid:105)p = UN (α, βp)UG(E, γp) 0.49
(4) where |s(cid:105) is the uniform superposition of bitstrings of length n, (4) |s(cid:105) は長さ n のビットストリングの一様重ね合わせである。 0.68
. . . UN (α, β1)UG(E, γ1)|s(cid:105) , . . . UN(α, β1)UG(E, γ1)|s(cid:105) 0.43
|s(cid:105) = s(cid:105) = 0.40
1√ 2n x∈{0,1}n 1~2n x ∈{0,1}n 0.40
|x(cid:105) , |x(cid:105)。 0.60
(5) (cid:88) (5) (cid:88) 0.41
5 FIG. 3: EQC used in this work. 5 FIG.3: この作業で使用されるEQC。 0.64
Each layer consists of two parts: the first part UG encodes edge features, while the second part UN encodes node features. 各層は2つの部分で構成され、第1部UGはエッジ特徴を符号化し、第2部UNはノード特徴を符号化する。 0.65
Each of the two parts is parametrized by one parameter βl, γl, respectively. 2つの部品はそれぞれ1つのパラメータβl,γlでパラメータ化される。 0.82
n(cid:79) UN (α, βj) with Rx(θ) = e−i θ n(キッド:79) rx(θ) = e−i θ を持つ un (α, βj) 0.75
2 X , is defined as 2 X と定義されている。 0.74
UN (α, βj) = UN(α, βj) = 0.47
Rx(αl · βj), Rx(αl · βj) 0.45
(6) and UG(E, γj) is (6) UG(E, γj) は 0.61
l=1 UG(E, γj) = exp(−iγjHG) l=1 ug(e, γj) = exp(−iγjhg) 0.50
with HG =(cid:80) hg =(cid:80)の場合 0.61
(7) and E are the edges of graph G weighted by εij. (7) と E は εij で重み付けられたグラフ G の辺である。 0.81
A 5-qubit example of this ansatz can be seen in fig. このアンザッツの5ビットの例はフィグで見ることができる。 0.50
3. (i,j)∈E εijσ(i) 3. (i,j)htmle εijσ(i) 0.42
z σ(j) z For p = 1, we have |E, α, β, γ(cid:105)1 = UN (α, β)UG(E, γ)|s(cid:105) z σ(j) z p = 1 に対して |E, α, β, γ(cid:105)1 = UN (α, β)UG(E, γ)|s(cid:105) を持つ。 0.87
· (cid:88) x∈{0,1}n ·(第88回) x ∈{0,1}n 0.53
· exp (cid:124) ·exp (cid:124) 0.39
α1β 2 cos (cid:18) (cid:124)  (cid:88) α1β 2 コス (出典:18)(出典:124)→(出典:88) 0.42
(i,j)∈E = 1√ 2n + ··· − isin (i,j)大E = 1 = 2n + ··· − isin 0.36
− ··· − isin --····-イシン 0.36
αlβ 2 (cid:123)(cid:122) αlβ2 (cid:123)(cid:122) 0.35
weighted bitflip terms 重み付きビットフリップ項 0.47
(cid:19) (cid:125) (第19回)(第125回) 0.51
αnβ 2 diag(ZiZj)|x(cid:105) · −i αnβ 2 diag(ZiZj)|x(cid:105) · −i 0.38
π 2 γεij |x(cid:105) , π 2 γεij |x(cid:105)。 0.58
(8) (cid:123)(cid:122) (8) (cid:123)(cid:122) 0.40
edge weights  (cid:125) エッジウェイト エイ(cid:125) 0.56
where diag(ZiZj)|x(cid:105) = ±1 is the entry in the matrix corresponding to each ZiZj term, e g , I1 ⊗···⊗ Zi ⊗ Ik⊗···⊗Zj⊗···⊗In, corresponding to the basis state |x(cid:105). ここで diag(ZiZj)|x(cid:105) = ±1 は、基底状態 |x(cid:105) に対応する各 ZiZj 項に対応する行列のエントリである。 0.73
(E.g., the first term on the diagonal corresponds to the all-zero state, and so on.) (例えば、対角線上の最初の項は、全ゼロ状態などに対応する。) 0.62
We see that the first group of terms, denoted weighted bitflip terms, is a sum over products of terms that encode the node features. 重み付きビットフリップ項と呼ばれる最初の項群は、ノードの特徴を符号化する項の積の和である。 0.53
In other words, in the one-qubit case we get a sum over sine and cosine terms, in the two-qubit case we get a sum over products of pairs of sine and cosine terms, and so on. 言い換えると、1量子ビットの場合、正弦項と正弦項の和が得られ、2量子ビットの場合は正弦項と正弦項の対の積の和が与えられる。
訳抜け防止モード: 言い換えると、ある- qubit の場合、sine と cosine の項の和が得られる。 2つの量子ビットの場合、正弦項と余弦項の対の積上の和が得られる。 など。
The terms in the second part of the equation denoted edge weights is the exponential of a sum over edge weight terms. 方程式の第2部における辺重みを表す項は、辺重み項上の和の指数関数である。 0.55
As we start in the uniform superposition, each basis state’s amplitude depends on all node and edge features, but with different signs and therefore different terms interfering constructively and destructively for every basis state. 一様重ね合わせから始めると、各基底状態の振幅は全てのノードとエッジの特徴に依存するが、異なる符号とそれゆえ各基底状態に対して建設的かつ破壊的に干渉する異なる用語を持つ。 0.79
This can be regarded as a quantum version of the classical aggregation functions in GNNs as discussed これはGNNにおける古典的集約関数の量子版と見なすことができる。 0.75
. . . 𝑈𝐺(ℰ, 𝛾1)one layer𝑈𝑁(𝛼, 𝛽1) . . . UG(E, γ1)オン層UN(α, β1) 0.68
in section II. Similarly to the classical case where the k-th layer of a NN aggregates information over the klocal neighborhood of the graph, the terms in eq. 第2節で 古典的な場合と同様に、NN の k 番目の層がグラフの局所的近傍(eq の項)に情報を集約する。 0.59
(8) become more complex with each additional layer in the PQC. (8)はPQCの各付加層とより複雑になる。 0.77
The reader may already have observed that this ansatz is closely related to an ansatz that is wellknown in quantum optimization: that of the quantum approximate optimization algorithm (QAOA) [9]. 読者は、このアンサッツが量子最適化でよく知られたアンサッツ(量子近似最適化アルゴリズム (qaoa) [9])と密接に関連していることを既に観察しているかもしれない。 0.73
Indeed, our ansatz can be seen as a special case of the QAOA, where instead of using a cost Hamiltonian to encode the problem, we directly encode instances of graphs and apply the “mixer terms” in eq. 実際、我々の ansatz はqaoa の特別な場合と見なすことができ、コストハミルトニアンを使って問題を符号化するのではなく、グラフのインスタンスを直接エンコードし、eq に "mixer terms" を適用する。 0.74
(6) only to available nodes. (6) 利用可能なノードのみ。 0.83
This correspondence will later let us use known results for QAOA-type ansatzes at depth one [40] to derive exact analytical forms of the expectation values of our ansatz, and use these to study its expressivity. この対応により、深度1[40]のQAOA型アンサーゼの既知の結果を用いて、我々のアンザッツの期待値の正確な解析形式を導出し、その表現性を研究することができる。 0.71
As our focus is on implementing an ansatz that respects a symmetry that is useful in graph learning tasks, namely an equivariance under permutation of vertices of the input graph, we now show that each part of our ansatz respects this symmetry. 我々の焦点は、グラフ学習タスク、すなわち入力グラフの頂点の置換の下での同値である対称性を尊重するアンサッツの実装であるので、我々のアンサッツの各部分がこの対称性を尊重していることが示される。 0.74
Theorem 1 (Permutation equivariance of the ansatz). 定理1(アンサッツの置換同値)。 0.48
Let the ansatz be of the type as defined in eq. ansatz を eq で定義されている型とする。 0.68
(4) with parameters β, γ ∈ Rp that represents an instance of a graph G with weighted edges εij ∈ E. Let P ∈ Bn×n be a permutation on the weighted adjacency matrix A of G, and ˜P ∈ B2n×2n a matrix that maps the tensor product |v1(cid:105)⊗|v2(cid:105)⊗···⊗|vn(cid:105) with |vi(cid:105) ∈ C2 to |vp(1)(cid:105) ⊗ |vp(2)(cid:105) ⊗ ··· ⊗ |vp(n)(cid:105). (4) パラメータ β, γ ∈ Rp は、重み付き辺 εij ∈ E を持つグラフ G のインスタンスを表す。 P ∈ Bn×n を G の重み付き随伴行列 A 上の置換とし、かつ、そのテンソル積 |v1(cid:105) を |vi(cid:105) ∈ C2 と |vp(1)(cid:105) ∈ C2 と |vp(2)(cid:105) ···|vp(cid:105) を写像する行列とする。 0.85
We call an ansatz that satisfies the following property equivariant under permutations of vertices in G, 我々は、G の頂点の置換の下で以下の性質同変を満たすアンザッツを呼ぶ。 0.60
|E, α, β, γ(cid:105)p = ˜P |E(P T AP ), α, β, γ(cid:105) |E, α, β, γ(cid:105)p = >P |E(P T AP ), α, β, γ(cid:105) 0.48
(9) with E(P T AP ) the graph edges after action of the permutation matrix on the adjacency matrix A of the given graph. (9) 与えられたグラフの隣接行列A上の置換行列の作用の後にグラフエッジをE(P T AP ) で表す。 0.81
, p As mentioned before, our ansatz is closely related to the EH-QGCs in [33], and the authors of this work prove the equivariance of this type of circuit for unweighted adjacency matrices. , p 前述したように、我々の ansatz は [33] における eh-qgcs と密接に関連しており、本論文の著者は、非重み付き隣接行列に対するこの種の回路の同値性を証明する。 0.49
In order to prove equivariance of our circuit, we have to generalize their result to the case where a weighted graph is encoded in form of a Hamiltonian and parametrized by a set of free parameters on these weights as described in eq. 回路の等価性を証明するためには、重み付きグラフがハミルトニアン形式で符号化され、eq で記述されるようなこれらの重み付け上の自由パラメータの集合によってパラメトリゼーションされる場合に、それらの結果を一般化する必要がある。 0.67
(4). In the non-parametrized case this is trivial, as edge weights are directly permuted as a consequence of the permutation of the adjacency matrix. (4). 非パラメータの場合、辺の重みは隣接行列の置換の結果として直接置換されるので、これは自明である。 0.53
When introducing parameters to the node and edge features however, we have to make sure that the parameters themselves preserve equivariance. しかし、ノードとエッジの機能にパラメータを導入する場合、パラメータ自体が等分散を保つようにする必要があります。 0.72
As the parameters are not tied to the adjacency matrix but to the circuit itself, they need to be invariant under permutations of the input graph. パラメータは隣接行列ではなく、回路自体に結びついているため、入力グラフの置換の下で不変である必要がある。 0.69
To guarantee this, we choose to assign one node and edge parameter per layer, respectively, and this makes us arrive at the QAOA-type parametrization shown in eq. これを保証するため、各層ごとに1つのノードとエッジパラメータを割り当てることを選択し、これはeqで示すQAOA型パラメトリゼーションに到達します。 0.81
(4). For didactic reasons we provide a formal proof of our circuit’s equivariance in appendix A. Note that we formulate the theorem (4). 道理上の理由から、付録Aにおける回路の等価性の形式的証明を提供する。 0.51
6 in terms of the state vector |E, α, β, γ(cid:105)p instead of the unitary 6) 単位元の代わりに状態ベクトル |E, α, β, γ(cid:105)p で表す。 0.78
UN (α, βp)UG(E, γp) . . . UN (α, β1)UG(E, γ1), UN (α, βp)UG(E, γp) . . UN (α, β1)UG(E, γ1) 0.45
as our initial state is always the uniform superposition. 初期状態は常に一様重ね合わせである。 0.59
The equivariance of this unitary holds regardless of the initial state, however, when choosing an initial state that is different from the uniform superposition, the equivariance of the state vector only holds if that initial state is permutation invariant. このユニタリの等式は初期状態に関係なく成り立つが、一様重ね合わせとは異なる初期状態を選択するとき、状態ベクトルの等式は初期状態が置換不変である場合にのみ成り立つ。 0.65
OPTIMIZATION WITH THE EQC In this section, we formally define the learning task that we address in this work, and the specific setup of the EQC and its observables. EQCによる最適化 本稿では,本研究で取り組んだ学習課題と,EQCとその観測装置の具体的設定を正式に定義する。 0.76
We show that each component of the QNCO scheme – Q-values and resulting tour – is equivariant under permutation of the vertices, and then analytically study the expressivity of our ansatz at depth one. QNCOスキームの各成分(Q-値と結果のツアー)が頂点の置換の下で同変であることを示し、それから深度1で我々のアンサッツの表現率を解析的に研究する。 0.69
A. Formal definition of learning task and figures A.学習課題と数字の形式的定義 0.80
of merit Our goal 功労者 我々のゴールは 0.53
is to use the ansatz described in section III to train a model that, once trained, implements a heuristic to produce tours for the TSP. 第3節で記述されたアンザッツを使用して、トレーニングが完了すれば、TSPのツアーを制作するためのヒューリスティックな実装を行うモデルをトレーニングする。
訳抜け防止モード: 第3節で記述された アンザッツを使用することです TSPのためのツアーを制作するヒューリスティックを実装したモデルをトレーニングする。
The TSP consists of finding a permutation of a set of cities such that the resulting length of a tour visiting each city in this sequence is minimal. TSPは、このシーケンスで各都市を訪れるツアーの長さが最小となるような、一連の都市の置換を見つけることで構成される。 0.75
The heuristic takes as input an instance of the TSP problem in form of a weighted 2D Euclidean graph G(V,E) with n = |V| nodes representing the cities and edge weights εij = d(vi, vj), where d(vi, vj) is the Euclidean distance between nodes vi and vj. ヒューリスティックは、重み付き2次元ユークリッドグラフ G(V,E) と n = |V| ノードが都市とエッジの重みを表す εij = d(vi, vj) の形で TSP 問題の例を入力として取り、d(vi, vj) はノード vi と vj の間のユークリッド距離である。 0.81
Specifically, we are dealing with the symmetric TSP, where the edges in the graph are undirected. 具体的には、グラフのエッジが無方向である対称的 TSP を扱う。 0.69
Given G, the algorithm constructs a tour in n − 2 steps. g が与えられると、アルゴリズムは n − 2 ステップでツアーを構成する。 0.74
Starting from a given (fixed) node in the proposed tour Tt=1, in each step t of the tour selection process the algorithm proposes the next node (city) in the tour. 提案するツアーtt=1の所定の(固定)ノードからスタートし、ツアー選択プロセスの各ステップtにおいて、アルゴリズムはツアー中の次のノード(都市)を提案する。 0.74
Once the secondbefore-last node has been added to the tour, the last one is also directly added, hence the tour selection process requires n−2 steps. 2番目のノードがツアーに追加されると、最後のノードも直接追加されるので、ツアー選択プロセスはn−2ステップを必要とする。 0.64
This can also be viewed as the process of successively marking nodes in a graph as they are added to a tour. これはまた、ツアーに追加されたグラフ内のノードを連続的にマーキングするプロセスと見なすこともできる。 0.78
In order to refer to versions of the input graph at different time steps where the nodes that are already present in the tour are marked, we now define the annotated graph. ツアーにすでに存在するノードがマークされている異なる時間ステップで入力グラフのバージョンを参照するために、アノテーション付きグラフを定義します。
訳抜け防止モード: 異なる時間ステップで入力グラフのバージョンを参照するために ツアーにすでに存在しているノードは マークされています アノテーション付きグラフを定義します
Definition 1 (Annotated graph). 定義 1 (注釈付きグラフ)。 0.41
For a graph G(V,E), we call G(V,E, α(t)) the annotated graph at time step t. グラフ g(v,e) に対して、時間ステップ t において g(v,e, α(t)) を注釈付きグラフと呼ぶ。 0.83
The vector α(t) ∈ {0, π}n specifies which nodes are already in the tour Tt (α(t) i = 0) and which nodes are still available for selection (α(t) ベクトル α(t) ∈ {0, π}n は、どのノードがツアー Tt (α(t) i = 0) にあり、どのノードがまだ選択できるか(α(t))を指定する。 0.78
i = π). i = π) である。 0.84
In each time step of an episode in the algorithm, the model is given an annotated graph as input. アルゴリズムにおけるエピソードの各タイムステップでは、入力として注釈付きグラフが与えられる。 0.72
Based on the annotated graph, the model should select the 注釈付きグラフに基づいて、モデルが選択すべき 0.82
next node to add to the partial tour Tt at step t. 次に、ステップtで部分ツアーttに追加するノード。 0.59
The annotation can be used to partition the nodes V into i = π} and the the set of available nodes Va = {vi|α(t) set of unavailable nodes Vu = {vi|α(t) i = 0}. このアノテーションは、ノード V を i = π {\displaystyle i} に分割し、利用可能なノードの集合 Vu = {vi|α(t) i = 0 {\displaystyle Vu= {vi|α(t)i=0} に分割するのに使うことができる。
訳抜け防止モード: このアノテーションはノード V を i = π } に分割するのに使うことができる。 そして、利用可能なノードの集合 Vu = { vi|α(t ) の集合 Vu = { vi|α(t ) i = 0 } である。
The node selection process can now be defined as follows. ノード選択プロセスは次のように定義できるようになった。 0.71
Definition 2 (Node selection). 定義2(ノードの選択)。 0.75
Given an annotated graph G(V,E, α(t)), the node selection process consist of selecting nodes in a tour in a step-wise fashion. 注釈付きグラフg(v,e,α(t))が与えられると、ノード選択プロセスは、ステップワイズでツアー中のノードを選択することで構成される。 0.76
To add a node to the partial tour Tt, the next node is selected from the set of available nodes Va. 部分ツアーTtにノードを追加するために、次のノードは利用可能なノードVaのセットから選択される。 0.76
The unavailable nodes Vu are ignored in this process. このプロセスでは、利用できないノードVuは無視される。 0.58
After n−2 steps, the model has produced a tour Tn. n−2ステップの後、このモデルはツアーTnを生成する。 0.70
A depiction of this process can be found in fig. この過程の描写は図に示されている。 0.65
2. To assess the quality of the generated tour, we compare the tour length c(Tn) to the length of the optimal tour c(T ∗), where 2. 生成したツアーの質を評価するために、ツアーの長さc(Tn)と最適なツアーの長さc(T∗)を比較する。 0.54
c(T ) = εij c(T ) = εij 0.41
(10) (cid:88) (10) (cid:88) 0.41
{i,j}∈ET i,j] ジャブレット. 0.35
is the sum of edge weights (distances) for all edges between the nodes in the tour, with ET ⊂ E. We measure the quality of the generated tour in form of the approximation ratio ツアー中のノード間のすべてのエッジのエッジ重み(距離)の和である ET は E である。 生成したツアーの質を近似比の形で測定する。 0.65
c(Tn) c(T ∗) c(Tn) c(T ∗) 0.38
. (11) The rewards in this environment are defined by the difference in overall length of the partial tour Tt at time step t, and upon addition of a given node vl at time step t + 1: . (11) この環境における報酬は、時間ステップtにおける部分ツアーTtの全体の長さの差と、時間ステップt+1における所定のノードvlの追加によって定義される。 0.51
r(Tt, vl) = −c(T(t+1,vl)) + c(Tt). r(tt, vl) = −c(t(t+1, vl)) + c(tt) である。 0.85
(12) Note that we use the negative of the cost as a reward, as a Q-learning agent will always select the action that leads to the maximum expected reward. (12) q-learningエージェントは常に最大報酬につながるアクションを選択するので、コストのマイナス値が報酬として使用されることに注意してください。 0.55
The learning process is defined in terms of a DQN algorithm, where the Q-function approximator is implemented in form of a PQC (which is described in detail in section III). 学習過程はDQNアルゴリズムで定義され、Q関数近似器はPQCとして実装される(第III節で詳述)。
訳抜け防止モード: 学習プロセスはDQNアルゴリズムによって定義される。 ここで、Q-関数近似器は、PQC(セクションIIIで詳しく説明されている)の形で実装されます。
Here, we define the TSP in terms of an RL environment, where the set of states S = {Gi(V,E, α(t)) for i = 1, . . . ,|X| and t = 1, . . . , n − 1} consists of all possible annotated graphs (i.e., all possible configurations of values of α(t)) for each instance i in the training set X . ここでは、TSP を RL 環境で定義する: i = 1, . . ,|X| および t = 1, . . . , n − 1} の状態 S = {Gi(V,E, α(t)) の集合は、トレーニング集合 X の各インスタンス i に対して可能なすべてのアノテートグラフ(すなわち、任意の α(t) の値の構成)からなる。 0.78
This means that the number of states in this environment is |S| = 2n−1|X|. これは、この環境における状態の数は |S| = 2n−1|X| であることを意味する。 0.51
The action that the agent is required to perform is selecting the next node in each step of the node selection process described in definition 2, so the action space A consists of a set of indices for all but the first node in each instance (as we always start from the first node in terms of the list of nodes we are presented with for each graph, so α(t) エージェントが実行するアクションは、定義2で記述されたノード選択プロセスの各ステップで次のノードを選択することであるので、アクション空間aは、各インスタンスの第1ノードを除くすべてのインデックスからなる(各グラフで提示されるノードのリストで、常に第1ノードからスタートするので、α(t))。
訳抜け防止モード: エージェントが実行するために必要なアクションは、定義2に記述されたノード選択プロセスの各ステップで次のノードを選択することである。 したがって、アクション空間 a は、各インスタンスの最初のノード以外のすべてのインデックスからなる(各グラフに対して提示されるノードのリストの観点で、常に最初のノードから開始するので)。 なので α(t )
1 = 0, ∀ t), and |A| = n − 1. 1 = 0 であり、|a| = n − 1 である。 0.80
The Q-function approximator gets as input an annotated graph, and returns as output the index of the node that should next be added to the tour. Q関数近似器は、アノテーション付きグラフとして入力され、次にツアーに追加すべきノードのインデックスとして出力される。 0.79
Which index this is, is decided in terms of measuring an observable on each qubit corresponding to the available nodes Va. これがどのインデックスかは、利用可能なノードVaに対応する各キュービット上の可観測値を測定する観点から決定される。 0.75
Depending on the last node added to the 最後のノードの追加次第です。 0.62
partial tour, denoted as vt−1, the observable for each available node vl is defined as vt−1 と表記される部分ツアーで、利用可能な各ノード vl に対する可観測性は、 0.66
Ovl = εvt−1,vl Zvt−1 Zvl Ovl = εvt−1,vl Zvt−1 Zvl 0.36
(13) weighted by the edge weight εvt−1,vl , and the Q-value corresponding to each action is (13) エッジウェイト εvt−1,vl で重み付けされ、各アクションに対応する Q-値が 0.58
7 Q(Gi(V,E, α(t)), vl) = 7 Q(Gi(V,E,α(t)), vl) = 0.40
(cid:104)E, α(t), β, γ|p Ovl |E, α(t), β, γ(cid:105)p , (cid:104)E, α(t), β, γ|p Ovl |E, α(t), β, γ(cid:105)p , 0.50
(14) where the exact form of |E, α(t), β, γ(cid:105)p is described in section III. (14) |e, α(t), β, γ(cid:105)p の正確な形が第iii節に記述されている。
訳抜け防止モード: (14) |E, α(t) の正確な形式 β , γ(cid:105)p は第III節で記述される。
All unavailable nodes vl ∈ Vu are not included in the node selection process, so we manually set their Q-values to a large negative number to exclude them, e g , すべての不利用可能なノード vl ∈ Vu はノード選択プロセスには含まれないので、Q-値を大きな負の数に手動で設定し、例えば、それらを排除する。 0.69
Q(Gi(V,E, α(t)), vl) = −10000 ∀ vl ∈ Vu. Q(Gi(V,E, α(t)), vl) = −10000 > vl ∈ Vu。 0.76
We also define a stopping criterion for our algorithm, which corresponds to the agent solving the TSP environment for a given instance size. また,tsp環境を与えられたインスタンスサイズで解くエージェントに対応するアルゴリズムの停止基準を定義する。
訳抜け防止モード: また,アルゴリズムの停止基準を定義する。 与えられたインスタンスサイズに対してTSP環境を解決するエージェントに対応する。
As we aim at comparing the results of our algorithm to optimal solutions in this work, we have access to a labeled set of instances and define our stopping criterion based on these. 本研究におけるアルゴリズムの結果と最適解を比較することを目的として,ラベル付きインスタンスの集合にアクセスし,これに基づいて停止基準を定義する。 0.78
However, note that the optimal solutions are not required for training, as a stopping criterion can also be defined in terms of number of episodes or other figures of merit that are not related to the optimal solution. しかし、最適解はトレーニングに必要ではないことに注意し、停止基準は最適な解とは無関係なエピソード数や他のメリットの数字で定義することもできる。
訳抜け防止モード: しかし、最適解は訓練に必要ではないことに注意。 停止基準として、エピソード数で定義することもできる。 または、最適解とは無関係なその他のメリットの数値。
In this work, the environment is considered as solved and training is stopped when the average approximation ratio of the past 100 iterations is < 1.05, where an approximation ratio of 1 means that the agent returns the optimal solution for the instances it was presented with in the past 100 episodes. 本研究では,過去100回の平均近似比が1.05である場合,1の近似比はエージェントが過去100回に提示したインスタンスに対して最適解を返すことを意味する。
訳抜け防止モード: 本研究では,過去100回の平均近似比が1.05となると,環境が解決され,トレーニングが中止される。 近似比が 1 であるということは エージェントは過去100エピソードで提示されたインスタンスに対して 最適な解決策を返します
We do not set the stopping criterion at optimality for two reasons: 2つの理由により、停止基準を最適に設定しない。 0.70
i) it is unlikely that the algorithm finds a parameter setting that universally produces the optimal tour for all training instances, and 一 アルゴリズムが全てのトレーニングインスタンスの最適ツアーを普遍的に生成するパラメータ設定を見つけることは不可能である。
訳抜け防止モード: i) ありそうにない アルゴリズムは、全てのトレーニングインスタンスに対する最適なツアーを普遍的に生成するパラメータ設定を見つけ、
ii) we want to avoid overfitting on the training data set. 二 トレーニングデータセットの過度な適合を避けること。 0.42
If the agent does not fulfill the stopping criterion, the algorithm will run until a predefined number of episodes is reached. エージェントが停止基準を満たしていない場合、事前に定義されたエピソード数に達するまでアルゴリズムが実行される。 0.74
In our numerical results shown in section V, however, most agents do not reach the stopping criterion of having an average approximation ratio below 1.05, and run for the predefined number of episodes instead. しかし,第5節で示された数値では,ほとんどのエージェントは平均近似比1.05未満の停止基準に達しず,あらかじめ定義されたエピソード数に対して実行している。 0.72
Our goal is to generate a model that is, once fully trained, capable of solving previously unseen instances of the TSP. 私たちのゴールは、TSPの未確認のインスタンスを解決できる、一度完全に訓練されたモデルを作ることです。 0.56
B. Equivariance of algorithm components B.アルゴリズム成分の等価性 0.75
We showed in section III A that our ansatz of arbitrary depth is permutation equivariant. セクションIIIAでは、任意の深さのアンサッツが置換同変であることを示した。 0.56
Now we proceed to show that the Q-values that are generated from measurements of this PQC, and the tour generation process as described in section IV A are equivariant as well. ここでは、このPQCの測定から生成されたQ値と、第IV節Aに記載されたツアー生成過程も同変であることを示す。 0.72
While the equivariance of all components of an algorithm is not a pre-requisite to harness the advantage gained by an equivariant model, knowing which parts of our learning strategy fulfill アルゴリズムの全ての成分の等価性は、同変モデルによって得られる利点を利用するための前提条件ではないが、我々の学習戦略のどの部分が満たされるかを知っている。
訳抜け防止モード: アルゴリズムのすべての成分の同値性は、同変モデルによって得られる利点を活用するための必要条件ではない。 学習戦略のどの部分が
this property provides additional insight for studying the performance of our model later. この特性は、後ほどモデルの性能を研究する上で、さらなる洞察を与えます。 0.65
As we show that the whole node selection process is equivariant, we know that the algorithm will always generate the same tour for every possible permutation of the input graph for a fixed setting of parameters, given that the model underlying the tour generation process is equivariant. ノード選択プロセス全体が同変であることが示されるように、ツアー生成プロセスの基盤となるモデルが同変であることを考えると、アルゴリズムは常にパラメータの固定設定に対して入力グラフの可能な置換ごとに同じツアーを生成する。 0.83
This is not necessarily true for a nonequivariant model, and simply by virtue of giving a permuted graph as input, the algorithm can potentially return a different tour. これは不同変モデルに必ずしも当てはまるものではなく、単に置換グラフを入力として与えることで、アルゴリズムは異なるツアーを返すことができる。 0.72
(Equivariance Theorem 2 of Q-values). (等) Q値の定理2)。 0.46
Let Q(Gi(V,E, α(t)), vl) as defined in eq. Q(Gi(V,E, α(t)), vl) を eq で定義する。 0.71
(14) be the Qvalue corresponding to vertex vl and graph Gi annotated with the nodes contained in the partial tour Tt at step t of a given episode. (14)は、あるエピソードのステップtにおける部分ツアーTtに含まれるノードに注釈を付した頂点vl及びグラフGiに対応するQ値である。 0.79
Let pn be a permutation of n = |V| elements, where the l-th element corresponds to the l-th vertex vl and pQ n be a permutation that reorders the Q-values Q(G(t) i ) = {Q(G(t) , vn)} in correspondence to the reordering of the vertices by pn. pn を n = |V| の元の置換とし、l 番目の元は l 番目の頂点 vl に対応し、pQ n は pn による頂点の再順序に対応する Q-値 Q(G(t) i ) = {Q(G(t) , vn)} を並べ替える置換とする。 0.83
Then Q(G(t) , vl) is equivariant under permutation of the vertices vl, このとき、Q(G(t) , vl) は頂点 vl の置換の下で同変である。 0.69
, v1), . . . , Q(G(t) , v1), . . . , q(g(t)) 0.41
i i i Q(G(t) 私は 私は 私は Q(G(t)) 0.52
i , vl) = Q(G(t,pn) 私は , vl) = Q(G(t,pn) 0.48
i , vpQ n (l)), 私は 、vpQ n (l)) である。 0.69
(15) where G(t,pn) vpQ mutation pn. (15) ここで G(t,pn) vpQ 変異 pn。 0.59
is the permuted graph at step t, and n (l) is the vertex corresponding to vl after the per- ステップ t の置換グラフであり、n (l) はper の後に vl に対応する頂点である。 0.76
i i Proof. We know from Theorem 1 that the ansatz that we use and therefore the expectation values (cid:104)Ovl(cid:105 ) are permutation equivariant. 私は 私は 証明。 定理1から、我々が使うアンサッツとそれゆえ期待値(cid:104)ovl(cid:105 )は置換同値であることがわかる。 0.57
The remaining terms in Q(G(t) , vl) (see eq. Q(G(t) , vl) の残りの項は eq である。 0.75
(14)) only depend on the edge weights of the graph G. The edge weights are computed according to the graph’s adjacency matrix, and are therefore re-ordered under a permutation of the vertices pn and assigned to their corresponding permuted expectation values. 辺重みはグラフの隣接行列に従って計算され、したがって頂点 pn の置換の下で再順序付けされ、対応する置換期待値に割り当てられる。
訳抜け防止モード: (14) ) はグラフ g の辺重みのみに依存し、辺重みはグラフ の隣接行列に従って計算される。 それゆえ、re--頂点pnの順列で順序付けされる そして、対応する置換された期待値に割り当てられる。
By this, all terms in Q(G(t) これにより、Q(G(t))のすべての項 0.84
, vl) are permutation equivariant. , vl) は置換同値である。 0.63
i As a second step to show that all components of our algorithm are permutation equivariant, it remains to show that the tours that our model produces as described in section IV A are also equivariant under permutations. 私は アルゴリズムのすべての成分が置換同変であることを示す第2のステップとして、第4節Aで記述されているように、我々のモデルが生成するツアーも置換同変であることが示される。 0.60
of (Equivariance Theorem 3 tours). ですから (等) 第3回)。 0.39
Let Tt(Gi, β, γ, v0) be a tour generated by a permutation equivariant agent implemented with a PQC as defined in Theorem 1 and Q-values as defined in Theorem 2, for a fixed set of parameters β, γ and a given start node v0, where a tour is a cycle over all vertices vl ∈ V that contains each vertex exactly once. tt(gi, β, γ, v0) を、定理 1 で定義される pqc と定理 2 で定義される q-値で実装された置換同変エージェントによって生成される巡回とし、与えられた開始ノード v0 に対して、tt(gi, β, γ, v0) を、各頂点をちょうど1度含むすべての頂点 vl ∈ v 上のサイクルとする。
訳抜け防止モード: Tt(Gi, β, γ, v0 ) を Theorem 1 と Q の値で定義される PQC で実装された置換同変エージェントによって生成されるツアーとする。 パラメータ β, γ と与えられた開始ノード v0 に対して、 ここで、ツアーは各頂点を正確に1度含むすべての頂点 vl ∈ V 上のサイクルである。
Let pn be a permutation of the vertices V. The output tour is equivariant under permutation of the vertices, pn を頂点 v の置換とし、出力 tour は頂点の置換の下で同値である。 0.54
Tt(Gi, β, γ, v0) = Tt(Gi,pn , β, γ, vpn(0)). tt(gi, β, γ, v0) = tt(gi,pn , β, γ, vpn(0))。 0.76
(16) Proof. We have shown in Theorem 2 that the Q-values of our model are permutation equivariant, meaning that a permutation of vertices results in a reordering (16) 証明。 我々はTheorem 2で、我々のモデルのQ-値が置換同変であること、つまり頂点の置換が再順序付けをもたらすことを示した。 0.57
8 i of Q-values to different indices. 8 私は 異なる指標に対するQ値の 0.59
Action selection is done by vt+1 = argmaxvQ(G(t) , v), and the node at the index corresponding to the largest Q-value is chosen. アクション選択は vt+1 = argmaxvQ(G(t) , v) で行われ、最大のQ値に対応するインデックスのノードが選択される。 0.84
To generate a tour, the agent starts at a given node v0 and sequentially selects the following n − 1 vertices. ツアーを生成するために、エージェントは与えられたノード v0 から始まり、次の n − 1 頂点を順次選択する。 0.72
Upon a permutation of the input graph, the tour now starts at another node index vpn(0). 入力グラフが置換されると、ツアーは別のノードインデックスvpn(0)から開始される。 0.73
Each step in the selection process can now be seen w.r.t. the original graph G(t) and the permuted graph G(t,pn) . 選択過程の各ステップは、元のグラフ G(t) と置換グラフ G(t,pn) の w.r.t で見ることができる。 0.88
As we have shown in Theorem 1, equivariance of the model holds for arbitrary input graphs, so in particular it holds for each G(t) in the action selection process, and the output tour under the permuted graph is equal to the output tour under the original graph up to a renaming of the vertices. Theorem 1 で示したように、モデルの等式は任意の入力グラフに対して成り立つので、特にアクション選択過程において各 G(t) に対して成り立ち、置換グラフの下での出力ツアーは元のグラフの下での出力ツアーに等しい。 0.68
and G(t,pn) そして G(t,pn) 0.80
i i i i 私は 私は 私は 私は 0.53
C. Analysis of expressivity In this section, we analyze under which conditions there exists a setting of β, γ for a given graph instance Gi for our ansatz at depth one that can produce the optimal tour for this instance. C. 表現性の分析 この節では、与えられたグラフインスタンス Gi に対する β, γ の設定が存在する条件を、この場合の最適ツアーを生成することができる深さ 1 で解析する。 0.73
Note that this does not show anything about constructing the optimal tour for a number of instances simultaneously with this set of parameters, or how easy it is to find any of these sets of parameters. これは、このパラメータセットと同時に複数のインスタンスの最適なツアーを構築することや、これらのパラメータセットを見つけるのがいかに簡単かについては何も示していない。 0.69
Those questions are beyond the scope of this work. これらの質問は、この仕事の範囲を超えている。 0.62
The capability to produce optimal tours at any depth for individual instances is of interest because first, we do not expect that the model can find a set of parameters that is close-tooptimal for a large number of instances if it is not expressive enough to contain a parameter setting that is optimal for individual instances. 個々のインスタンスに対して任意の深さで最適なツアーを生成する能力は、まず、各インスタンスに最適なパラメータ設定を含まないような表現がなければ、多数のインスタンスに対して最適に近いパラメータセットを見つけることができると期待できないため、興味深い。 0.68
Second, the goal of a ML model is always to find similarities within the training data that can be used to generalize well on the given learning task, so the ability to find optimal solutions on individual instances is beneficial for the goal of generalizing on a larger set of instances. 第二に、MLモデルの目標は、与えられた学習タスクをうまく一般化するために使用できるトレーニングデータの中で、常に類似点を見つけることである。
訳抜け防止モード: 第2に mlモデルの目標は 与えられた学習タスクをうまく一般化するために使用できるトレーニングデータ内の類似点を見つける。 したがって、個々のインスタンスで最適なソリューションを見つける能力は、より大きなインスタンスセットを一般化する目的に有益である。
Additionally, how well the model generalizes also depends on the specific instances and the parameter optimization routine, and therefore it is hard to make formal statements about the general case where we find one universal set of parameters that produces the optimal solution for arbitrary sets of instances. さらに、モデルがいかにうまく一般化するかは、特定のインスタンスとパラメータ最適化ルーチンに依存するため、任意のインスタンス集合に対して最適な解を生成する1つのパラメータの普遍的な集合を見つけるという一般的なケースについて形式的に記述することは困難である。 0.76
For our model at p = 1, we can compute the analytic form of the expectation values of our circuit as defined in eq. p = 1 のモデルの場合、eq で定義された回路の期待値の解析形式を計算することができる。 0.74
(13) and eq. (13)およびeq。 0.77
(14) as the following, by a similar derivation as in [40], (14)[40]と同様な導出により,次の通り 0.67
(cid:104)Ovl(cid:105 ) = εvt−1,vl · sin(βπ) sin(εvt−1,vl γ) (cid:104)Ovl(cid:105 ) = εvt−1,vl · sin(βπ) sin(εvt−1,vl γ) 0.40
· (cid:89) (vl,k)∈E k(cid:54)=vt−1 ·(第89回) (vl,k)・Ek(cid:54)=vt−1 0.54
cos(εvl,kγ), cos(εvl,kγ) 0.46
(17) where vt−1 is the last node in the partial tour and vl is the candidate node. (17) vt−1 は部分巡回の最後のノードであり、vl は候補ノードである。 0.61
In order to generate an arbitrary tour of our choice, in particular also the optimal tour, it suffices to guarantee that for a suitable choice of (fixed) γ, at each step in the node selection process the edge we want to add next to the partial tour has 私たちの選択した任意のツアー、特に最適なツアーを生成するには、適切な選択(固定)γに対して、ノード選択プロセスの各ステップにおいて、部分的なツアーの隣で追加したいエッジが持つことを保証するのに十分です。 0.71
highest expectation. One way we can do this is by controlling the signs of each sine and cosine term in eq. 期待が最も高い。 これを可能にする一つの方法は、eqにおける各サインとコサイン項の符号を制御することである。
訳抜け防止モード: 期待が最も高い。 この方法の1つは eqのsine と cosine の各項の記号を制御しています
(17) such that only the expectation values corresponding to edges that we want to select are positive, and all others are negative. 17) 選択したい辺に対応する期待値のみが正で、他のすべての値が負であるように。 0.74
To understand whether this is possible, we can leverage known results about the expressivity of the sine function. これが可能かどうかを理解するために、正弦関数の表現性に関する既知の結果を活用することができる。 0.58
First, it is known that the function class f まず、関数類 f が知られている。 0.76
(x) = sign(sin(xω)) parametrized by a single realvalued parameter ω has infinite Vapnik-Chervonenkisd imension (VC-dimension), also called shattering dimension. (x) = sign(sin(xω)) 単一の実数値パラメータ ω によってパラメータ化され、無限のvapnik-chervonenkisd imension (vc-dimension) を持つ。 0.75
Definition 3 (VC-dimension). 定義3(VC次元)。 0.39
Let X = {x1, . . . , xn} be a set of n data points labeled with binary labels in Y = {y1, . . . , yn}. X = {x1, . . . , xn} を Y = {y1, . . . . , yn} のバイナリラベルでラベル付けした n 個のデータ点の集合とする。 0.81
The set of points X is said to be shattered by a function class F if for all y ∈ Y n there exists a function f ∈ F s.t. f 点 X の集合は、すべての y ∈ Y n に対して函数 f ∈ F s.t. f が存在するとき、函数類 F によって破られると言われる。 0.83
(xi) = yi, i = 1, . . . , n. (xi) = yi, i = 1, . . , n。 0.39
The VC-dimension of a function class F is the size of the largest set of points that can be shattered by F. 関数類 F の VC-次元は、F によって破れる最大の点の集合の大きさである。 0.80
This result states that there exists at least one data set of infinite size that can be shattered by the function class f (x) = sign(sin(xω)), and a typical example of such a set is {2−m : m ∈ N} [41]. この結果は、関数類 f (x) = sign(sin(xω)) によって破砕できる無限サイズの少なくとも1つのデータセットが存在し、そのような集合の典型的な例は {2−m : m ∈ N} [41] である。 0.89
It does not tell us, however, if an arbitrary set of distinct points with labels in ±1 can be shattered by this function class. しかし、±1 のラベルを持つ任意の異なる点の集合が、この関数クラスによって破壊されるかどうかはわからない。 0.70
In fact, it is known that this is not the case, and one can easily show that the simple set of evenly spaced points {x, 2x, 3x, 4x} with x ∈ R can not be shattered by f (x) [41]. 実際、これはそうではないことが知られており、x ∈ R の等間隔点 {x, 2x, 3x, 4x} の単純集合が f (x) [41] で破れないことを容易に示せる。 0.74
To understand whether we can use the sine function to produce the labeling of edge weights of our choice, we can turn to another result, namely that for any rationally independent set of {x1, ..., xn} with labels yi ∈ (−1, 1), the sine function can approximate these points to arbitrary precision  as shown in [42], i.e., 我々の選択した辺重み付けのラベル付けをsine関数で生成できるかどうかを理解するために、別の結果、すなわちラベル yi ∈ (−1, 1) を持つ任意の有理独立な {x1, ..., xn} に対して、sine関数はこれらの点を[42] に示されるような任意の精度に近似することができる。 0.82
|sin(ωxi) − yi| <  for i = 1, . . . , n. i = 1 に対して |sin(ωxi) − yi| < . , n である。 0.93
(18) In general, the edge weights of graphs that represent TSP instances are not rationally independent.1 (18) 一般に、TSPインスタンスを表すグラフの辺重みは合理的に独立ではない。 0.57
However, in principle they can easily be made rationally independent by adding a finite perturbation (cid:48) i to each edge weight. しかし、原理的には、各辺の重みに有限摂動 (cid:48) i を加えることで、合理的に独立にすることができる。 0.69
The results in [42] imply that almost any set of points x1, . . . , xn with 0 < xi < 1 is rationally independent, so we can choose (cid:48) i to be drawn uniformly at random from (0, max]. 42] の結果は、ほとんどすべての点 x1, . . , . , xn の 0 < xi < 1 は有理独立であることを意味するので、 (0, )max] からランダムに描画される s(cid:48) i を選べる。 0.81
As long as these perturbations are applied to the edge weights in a way that does not change the optimal tour, as could be done by ensuring that max is small enough so that the proportions between edge weights are preserved, we can use this perturbed version of the graph to infer the optimal tour. これらの摂動が最適なツアーを変えない方法でエッジウエイトに適用されている限り、例えば、端ウエイト間の比率が保存されるほど、maxが十分に小さいことを保証して、最適なツアーを推測するために、この摂動バージョンのグラフを使用することができる。 0.63
(Such an max can be computed efficiently.) (この場合、maxは効率的に計算できる。) 0.84
In this way we can guarantee that the ansatz このようにして、アンザッツが保証される 0.37
1 The real numbers x1, . . . , xn are said to be rationally independent if no integers k1, . . . , kn exist such that x1k1 +· · · + xnkn = 0, besides the trivial solution ki = 0 ∀ k. 1 実数 x1, . . . . , xn が有理独立であるとは、整数 k1, . . . . . . , kn が存在して x1k1 +· · · + xnkn = 0 が成立するときに言う。 0.78
Rational independence also implies the points are not rational numbers, so they are also not numbers normally represented by a computer. 論理的独立性はまた、点が有理数ではないことを意味するため、通常はコンピュータで表される数ではない。 0.68
9 at depth one can produce arbitrary labelings of our edges, which in turn let us produce expectation values such that only the ones that correspond to edges in the tour of our choice will have positive values. 9 深さでは、エッジの任意のラベリングを生成でき、その結果、私たちの選択のツアーのエッジに対応するものだけが正の値を持つように、期待値を生成することができます。 0.55
We note that in the analysis we assume real-valued (irrational) perturbations, which of course cannot be represented in the computer. 解析では、実数値(非有理)摂動を仮定し、もちろんコンピュータでは表現できないことに注意する。 0.64
However, by using the results of [42] and approximating ±1 within a small epsilon, we can get a robust statement where finite precision suffices. しかし、[42]の結果と小さなエプシロン内で±1を近似することにより、有限精度が十分であるようなロバストなステートメントが得られる。 0.76
For completeness, we provide a proof for this case in section IV C. We, however do not go deeper into this discussion since in fact we do not want to rely on this proof of optimality as a guiding explanation of how the algorithm works. しかし、我々は、アルゴリズムの動作の指導的説明として、この最適性の証明に頼ることを望まないので、この議論に深くは触れない。
訳抜け防止モード: 完全性については、第IV節Cでこのケースの証明を提供する。 しかし この議論には 深く踏み込んではいけません この最適性の証明を アルゴリズムの仕組みの説明に頼っています
The reason for this is that in some way, this proof of optimality works despite the presence of the TSP graph and not because of it. その理由は、ある意味では、この最適性の証明は TSP グラフの存在にもかかわらず機能し、そのためではないからである。 0.75
This is similar in vein to universality results for QAOA-type circuits, where it can be shown that for very specific types of Hamiltonians, alternating applications of the cost and mixer Hamiltonian leads to quantum computationally universal dynamics, i.e. it can reach all unitaries to arbitrary precision [43, 44], but these Hamiltonians are not related to any of the combinatorial optimization problems that were studied in the context of the QAOA. これはQAOA型回路の普遍性の結果と類似しており、非常に特定の種類のハミルトニアンに対して、コストとミキサーの交互適用は量子的普遍力学、すなわち全てのユニタリを任意の精度(43, 44)まで到達できることを示しているが、これらのハミルトニアンはQAOAの文脈で研究された組合せ最適化問題とは無関係である。 0.76
While these results provide valuable insight into the expressivity of the models, in our case they do not inform us about the possibility of a quantum advantage on the learning problem that we study in this work. これらの結果はモデルの表現性に関する貴重な知見を提供するが、この場合、この研究で研究している学習問題に対する量子的優位性の可能性について、これらの結果は私たちに知らせない。 0.60
In particular, we do not know from these results whether the EQC utilizes the information provided by the graph features in a way in which the algorithm benefits from the quantumness of the model, at depth one or otherwise. 特に、これらの結果から、EQCがグラフの特徴によって提供される情報を利用して、アルゴリズムがモデルの量子性、深さ1以上の利点を享受できるかどうかがわからない。 0.69
As it is known that the QAOA applied to ground state finding benefits from interference effects, investigating whether similar results hold for our algorithm is an interesting question that we leave for future work. qaoaが干渉効果の恩恵を受ける基盤状態に適用されていることが知られているので、同様の結果がアルゴリズムに与える影響を調査することは、我々が今後の作業のために残した興味深い疑問である。
訳抜け防止モード: QAOAは、干渉効果の恩恵を受ける基底状態に適用されたことが知られている。 同様の結果が我々のアルゴリズムに 今後の仕事のために出発する 興味深い質問です
Additionally, we note that high expressivity alone does not necessarily lead to a good model, and may even lead to issues in training as the well-studied phenomenon of barren plateaus [15], or a susceptibility to overfitting on the training data. さらに,高い表現性は必ずしもよいモデルにつながりませんし,不毛高原[15]のよく研究された現象や,トレーニングデータへの過度な適合性といったトレーニングの問題にもつながります。 0.74
In practice, the best models are those that strike a balance between being expressive enough, and also restricting the search space of the model in a way that suits the given training data. 実際、最良のモデルは、十分な表現力を持つことと、与えられたトレーニングデータに適合する方法でモデルの検索空間を制限することのバランスをとるものである。 0.78
Studying and designing models that have this balance is exactly the goal of geometric learning, and the equivariance we have proven for our model is a helpful geometric prior for learning tasks on graph inputs. このバランスを持つモデルの研究と設計は、まさに幾何学的学習の目標であり、我々がモデルで証明した等分散性は、グラフ入力のタスクを学習する上で有用な幾何学的課題である。 0.71
V. NUMERICAL RESULTS A. Comparison of the EQC and non-equivariant V.数値結果 A. EQC と非同変の比較 0.75
ansatzes on the TSP After proving that our model is equivariant under node permutations and analytically studying the expressivity of our ansatz, we now numerically study the training and validation performance of this model TSPのアンサーゼ 我々のモデルがノード置換の下で同変であることを証明し, ansatzの表現性について解析的に研究した後, このモデルのトレーニングと検証性能を数値的に検討した。 0.67
10 FIG. 4: One layer of each of the circuits studied in this work. 10 第4図: この研究で研究された各回路の1つの層。 0.62
a) The EQC with two trainable parameters β, γ per layer. a) 2つの訓練可能なパラメータβ,γを層ごとに持つeqc。 0.67
b) The same set of gates as in the EQC, but we break equivariance by introducing one individual free parameter per gate (denoted NEQC). b) EQCと同じゲートの集合ですが、ゲートごとに1つの個別自由パラメータ(NEQCと表記)を導入することで、等価性を破ります。 0.72
c) Similar to the NEQC, but we start from the all-zero state and add a final layer of trainable one-qubit gates and a ladder of CZ-gates (denoted hardware-efficient with trainable encoding, HWETE). c) NEQCと同様、全ゼロ状態から開始し、トレーニング可能な1量子ビットゲートとCZゲートのラグ(ハードウェア効率とトレーニング可能なエンコーディングを備えたHWETE)の最終レイヤを追加します。 0.71
d) Same as the HWETE, but only the single-qubit Y-rotation parameters are trained (denoted HWE). d) HWETEと同じだが、単一のキュービットY回転パラメータのみを訓練する(HWEを参照)。 0.75
on TSP instances of varying size in a NCO context. NCOコンテキストにおける様々なサイズのTSPインスタンス。 0.77
The training data set that we use is taken from [3], where the authors propose a novel classical attention approach and evaluate it on a number of geometric learning tasks.2 使用したトレーニングデータセットは [3] から抽出され, 著者らは新しい古典的注意法を提案し, 幾何的学習タスクで評価する。 0.67
To compute optimal solutions for the TSP instances with 10 and 20 cities we used the library Python-TSP [45]. 10と20の都市でTSPインスタンスの最適なソリューションを計算するために、Python-TSP [45]ライブラリを使用しました。 0.66
We evaluate the performance of the EQC on TSP instances with 5, 10 and 20 cities (corresponding to 5, 10, and 20 qubits, respectively). 我々は,5,10,20都市(それぞれ5,10,20キュービット)のTSPインスタンス上でのEQCの性能を評価した。 0.71
As described in section IV A, the environment is considered as solved by an agent when the running average of the approximation ratio over the past 100 episodes is less than 1.05. 第4節Aに記載されているように、過去100回における近似比のランニング平均が1.05未満である場合には、エージェントによって環境が解決されると考えられる。 0.69
Otherwise, each agent will run until it reaches the maximum number of episodes, that we set to be 5000 for all agents. さもなくば、各エージェントは最大エピソード数に達するまで実行され、すべてのエージェントに対して5000に設定されます。 0.80
Note that this is merely a convenience to shorten the overall training times, as we have access to the optimal solutions of our training instances. トレーニングインスタンスの最適なソリューションにアクセスできるので、これは単にトレーニング時間を短縮するための利便性に留意してください。 0.73
In a realistic scenario where one does not have access to optimal solutions, the algorithm would simply run for a fixed number of episodes or until another convergence criterion is met. 最適解にアクセスできない現実的なシナリオでは、アルゴリズムは単に一定回数のエピソードに対して実行されるか、あるいは別の収束基準を満たすまで実行される。 0.72
When evaluating the final average approximation ratios, we always use the parameter setting that was stored in the final episode, regardless of the final training error. 最終平均近似比を評価する際には、最終訓練誤差にかかわらず、最終エピソードに格納されたパラメータ設定を常に使用します。 0.77
When 2 We note that we have re-computed the optimal tours for all instances that we use, as the data set uploaded by the authors of [3] erroneously contains sub-optimal solutions. いつ 2]の著者がアップロードしたデータセットには、誤ってサブ最適化ソリューションが含まれているので、使用するすべてのインスタンスの最適なツアーを再計算しました。 0.67
This was confirmed with the authors, but at the time of writing of this work their repository has not been updated with the correct solutions. これは著者によって確認されたが、この作業の執筆時点では、リポジトリは正しいソリューションで更新されていない。 0.72
variations in training lead to a slightly worse performance than what was achieved before, we still use the final parameter setting. トレーニングのバリエーションは、以前よりもわずかにパフォーマンスが悪くなりますが、最終的なパラメータ設定を使用します。 0.68
We do this because as noted above, in a realistic scenario one does not have knowledge about the ratio to the optimal solutions during training. これは、上述したように、現実的なシナリオではトレーニング中の最適解に対する比率について知識がないからである。 0.76
Unless otherwise stated, all models are trained on 100 training instances and evaluated on 100 validation instances. そうでなければ、すべてのモデルは100のトレーニングインスタンスでトレーニングされ、100の検証インスタンスで評価される。 0.67
As we are interested in the performance benefits that we gain by using an ansatz that respects an important graph symmetry, we compare our model to versions of the same ansatz where we gradually break the equivariance property. 重要なグラフ対称性を尊重するansatzを使用することで得られるパフォーマンス上のメリットに興味を持つので、このモデルを同じansatzのバージョンと比較します。 0.63
We start with the simplest case, were the circuit structure is still the same as for the EQC, but instead of having one βl, γl in each layer, every X- and ZZ-gate is individually parametrized. 最も単純な場合から始めると、回路構造はEQCと同じであるが、各層に1つのβl, γlを持つ代わりに、各X-およびZZ-ゲートは個別にパラメトリズされる。 0.85
As these parameters are now tied directly to certain one- and two-qubits gates, e g an edge between qubits one and two, they will not change location upon a graph permutation and therefore break equivariance. これらのパラメータは、例えば qubits 1 と 2 の間の辺のような、ある 1 と 2 つのキュービットゲートに直接結びつくので、グラフの置換によって位置が変わることはない。 0.74
We call this the non-equivariant quantum circuit (NEQC). これを非同変量子回路(NEQC)と呼ぶ。 0.83
To go one step further, we take the NEQC and add a variational part to each layer that is completely unrelated to the graph structure: namely a hardware-efficient layer that consists of parametrized Y-rotations and a ladder of CZ-gates. さらに一歩進めると、NEQC をグラフ構造とは無関係な各層、すなわちパラメタライズされた Y-回転と CZ-ゲートのはしごからなるハードウェア効率の高い層に追加する。 0.62
In this ansatz, we have a division between a data encoding part and a variational part, as is often done in QML. このアンサッツでは、QMLでよく行われるように、データ符号化部と変分部を分割する。 0.56
To be closer to standard types of ansatzes often used in QML, we also omit the initial layer of H-gates here and start from the all-zero state (which requires us QMLでよく使われる標準タイプのアンサツェに近づき、ここではHゲートの初期層を省略し、全ゼロの状態から始める(これは私たちを必要とする)。 0.71
b) NEQCc) HWETEd) HWEa) EQC b) NEQCc) HWETEd) HWEa) EQC 0.42
11 (a) Training performance, 1 layer 11 (a)訓練成績、1層 0.53
(b) Validation performance, 1 layer (b)検証性能、1層 0.73
(c) Training performance, 4 layers (c)訓練性能、4層 0.36
(d) Validation performance, 4 layers (d)検証性能、4層 0.36
FIG. 5: Comparison between the EQC and its non-equivariant version (NEQC) where each gate is parametrized separately as described in section V. Results are shown on TSP instances with 5, 10 and 20 cities (TSP5, TSP10 and TSP20, respectively), averaged over ten agents each. 第5章:各ゲートが第5節に記載されているように個別にパラメトリケートされるEQCと非同変バージョン(NEQC)の比較。その結果は,5,10,20都市(TSP5,TSP10,TSP20)のTSPインスタンスでそれぞれ10以上のエージェントで示される。 0.84
To provide a classical baseline, we also show results for the nearest-neighbor heuristic (NN). 古典的ベースラインを提供するため,最寄りヒューリスティック (NN) の結果も示す。 0.56
a) and b) show the training and validation performance for both ansatzes with one layer, while a) と b)一方の層を有する双方のアンサーゼの訓練及び検証性能を示す。 0.78
c) and d) show the same for four layers. c) と d) 4層でも同様を示す。 0.81
The dashed, grey line on the left-hand side figures denotes optimal performance. 左側の破れた灰色の線は最適な性能を示している。 0.70
The dotted, black line on the right-hand side figures denotes the upper bound of the Christofides algorithm, a popular classical approximation algorithm that is guaranteed to find a solution that is at most 1.5 times as long as the optimal tour. 右側の図形の点線の黒い線は、クリストフィデスアルゴリズムの上限を表しており、これは古典的な近似アルゴリズムであり、最適ツアーの1.5倍の解を見つけることが保証されている。 0.67
Figures a) and c) show the running average over the last ten episodes. 図 a) と c)過去10回のランニング平均を示す。 0.67
to switch the order of X- and ZZ-gates)3. xゲート及びzzゲートの順番を切り替える)3。 0.57
We denote this the hardware-efficient with trainable embedding (HWETE) ansatz. ハードウェア効率をトレーニング可能な埋め込み(hwete) ansatzで表します。 0.55
Finally, we study a third ansatz, where we take the HWETE and now only train the Yrotation gates, and the graph-embedding part of the circuit only serves as a data encoding step. 最後に、HWETEを学習し、Yrotationゲートのみを訓練する第3のアンサッツについて検討し、回路のグラフ埋め込み部分はデータ符号化のステップとしてのみ機能する。 0.74
We call this simply the hardware-efficient (HWE) ansatz. これを単にハードウェア効率(hwe)アンサッツと呼ぶ。 0.67
A depiction of all ansatzes can be seen in fig. すべてのアンサッチの描写は、図で見ることができる。 0.54
4. We start by comparing the EQC to the NEQC on TSP instances with 5, 10 and 20 cities. 4. まず、TSPインスタンス上のEQCとNEQCを比較し、5、10、20の都市を比較します。 0.55
We show the training and validation results in fig. 訓練と検証の結果を図で示します。 0.67
5. To evaluate the performance of the models that we study, we com- 5. 私たちが研究しているモデルの性能を評価するために、我々はまとめる。 0.52
pute the ratio to the optimal tour length as shown in eq. eqに示すように、最適なツアー長さに対する比率を割り当てる。 0.71
(11), as the instances that we can simulate the circuits for are small enough to allow computing optimal tours for.4 (11) 回路をシミュレートできるインスタンスは、.4の最適なツアーを計算できるほど小さい。 0.62
To provide an additional classical baseline, we also show results for the nearest-neighbor heuristic. さらに古典的ベースラインを提供するため、最寄りのヒューリスティックの結果も示す。 0.51
This heuristic starts at a random node and selects the closest neighboring node in each step to generate the final tour. このヒューリスティックはランダムなノードから始まり、各ステップで最も近い隣接ノードを選択して最終ツアーを生成する。 0.80
The nearest-neighbor algorithm finds a solution quickly also for instances with increasing size, but there is no guarantee that this tour is close to the optimal one. 最寄りのneighborアルゴリズムは、サイズが大きくなるインスタンスでも素早く解を見つけるが、このツアーが最適なものに近いという保証はない。 0.72
However, as we know the optimal tours しかし 最適なツアーを知っていれば 0.72
3 However, in practice it did not make a difference whether we started from the all-zero or uniform superposition state in the learning task that we study. 3) 実際には, 学習課題における全ゼロ・一様重ね状態から始めたか, あるいは一様重ね状態から始めたかは, 差はなかった。
訳抜け防止モード: 3 実際には 違いはありませんでしたが 研究対象の学習課題において,すべての-ゼロあるいは一様重ね合わせ状態から開始した。
4 For reference, the authors of [3], who generated the training instances that we use, stop comparing to optimal solutions at n = 20 as it becomes extremely costly to find optimal tours from thereon out. 参考までに、私たちが使用するトレーニングインスタンスを作成した[3]の著者は、そこから最適なツアーを見つけるのに非常にコストがかかるため、n = 20で最適なソリューションを比較するのをやめました。 0.64
02004006008001000Epi sode1.001.251.501.75 o to optimal tour lengthEQC-TSP5EQC-TS P10EQC-TSP20NEQC-TSP 5NEQC-TSP10NEQC-TSP2 0TSP5TSP10TSP201.01. mation ratioEQCNEQCNN020040 06008001000Episode1. 001.251.501.752.002. 252.502.75Ratio to optimal tour lengthEQC-TSP5EQC-TS P10EQC-TSP20NEQC-TSP 5NEQC-TSP10NEQC-TSP2 0TSP5TSP10TSP201.01. mation ratioEQCNEQCNN 02004006008001000Epi sode1.001.251.501.75 2.502.75Ratio toOptiimal Tour lengthEQC-TSP5EQC-TS P10EQC-TSP20NEQC-TSP 20NEQC-TSP20TSP5TSP2 .5Approximation ratioEQCNEQCNN200400 6001000Episode1.001. 251.501.752.502.75Ra tio toOptitimal Tour lengthEQC-TSP5EQC-TS P10EQC-TSP20QC-TSP20 QC-TSP20TSP10TSP20TS P20TSP20TSP20TSP20TS P20TSP201.01.11.211. 41.5AProximation ratioEQCNQC200400600 600Episode1.0.251.50 1.252.502.75Ratio toOptitimal Tour lengthEQC-TSP5EQC-TS P10EQC-TSP10EQC-TSP1 0EQC-TSP20QC-TSP20QC -TSP20TSP10111111111 111111111.11.11.111. 41.51.5Proximation ratioEQC 0.04
12 (a) TSP5, 1 layer 12 (a)TSP5,1層 0.44
(b) TSP5, 4 layers (b)TSP5、4層 0.43
(c) TSP10, 1 layer (c)TSP10,1層 0.46
(d) TSP10, 4 layers (d)TSP10,4層 0.46
FIG. 6: Comparison between EQC and two hardware-efficient ansatzes where we gradually break the equivariance of the original ansatz. 第6図:eqcとハードウェア効率の良い2つのansatzeの比較。
訳抜け防止モード: fig . 6: eqc と 2 つのハードウェアの比較 - 効率的な ansatzes where 元のアンサッツの等分散を徐々に壊す。
We show results for TSP instances with five and ten cities (TSP5, TSP10 respectively) for models trained on 10 and 100 instances, and with one and four layers. 5都市10都市(TSP5,TSP10)のTSPインスタンスに対して,10インスタンス,100インスタンス,および1レイヤ,4レイヤでトレーニングしたモデルについて結果を示した。 0.73
Each box is computed over results for ten agents. 各ボックスは10のエージェントの結果で計算される。 0.76
The hardware-efficient ansatz with trainable embedding (HWETE) consists of trainable graph encoding layers as those in the EQC, with an additional variational part in each layer that consists of parametrized single-qubit Y-gates and a ladder of CZ-gates. トレーニング可能な埋め込み(HWETE)付きハードウェア効率アンサッツは、トレーニング可能なグラフ符号化層をEQCと同様に構成し、各層にパラメタライズされたシングルキュービットYゲートとCZゲートのはしごからなる変分部を付加する。 0.69
The HWE ansatz is the same as the HWETE, but where the graph-embedding part is not trainable and only the Y-gates in each layer are trained. HWEアンサッツはHWETEと同じであるが、グラフ埋め込み部はトレーニング不可能であり、各層内のYゲートのみがトレーニングされる。 0.68
We also show approximation ratios of a random algorithm, where a random tour is picked as the solution to each instance. また、ランダムなツアーが各インスタンスの解として選択されるランダムなアルゴリズムの近似比を示す。 0.64
The dotted, black lines denote the upper bound of the Christofides algorithm. 点在する黒い線は、クリストフィデスアルゴリズムの上限を表す。 0.54
We see that the HWE ansatzes perform extremely badly and barely outperform picking random tours only in some cases. hwe ansatzesの成績は極めて悪く、一部のケースではランダムツアーのピッキングをほとんど上回っていない。 0.57
for all instances, the nearest-neighbor heuristic provides an easy to understand classical baseline that we can use. すべての例において、最寄りのヒューリスティックは、私たちが使える古典的なベースラインを簡単に理解できます。 0.55
Additionally, we add the upper bound given by one of the most widely used approximation algorithms for the TSP (as implemented e g in Google OR-Tools): the Christofides algorithm. さらに、TSP(Google OR-Toolsでegとして実装されている)の最も広く使われている近似アルゴリズムの1つであるChristofidesアルゴリズムの上限を追加する。 0.75
This algorithm is guaranteed to find a tour that is at most 1.5 times as long as the optimal tour [46]. このアルゴリズムは、最適なツアー[46]の1.5倍の長さのツアーを見つけることが保証されている。 0.75
In the case where any of our models produces validation results that are on average above this upper bound of the Christofides algorithm, we consider it failed, as it is more efficient to use a polynomial approximation algorithm for these instances. 私たちのモデルのいずれかが、クリストフィデスアルゴリズムのこの上限を超える平均値の検証結果を生成する場合、これらのインスタンスに対して多項式近似アルゴリズムを用いることがより効率的であるため、失敗すると考える。 0.84
The bound is shown as a dotted black line in fig. 境界線は、フィグの点線の黒い線として示される。 0.63
5 and fig. 6. Geometric learning models are expected to be more data-efficient than their unstructured counterparts, as 5および5。 6. 幾何学的学習モデルは、非構造化モデルよりもデータ効率が高いことが期待される。 0.59
they respect certain symmetries in the training data. 訓練データの特定の対称性を尊重します 0.72
This means that when a number of symmetric instances are present in the training or validation data, the effective size of these data sets is decreased. これは、トレーニングデータや検証データに多数の対称インスタンスが存在する場合、これらのデータセットの有効サイズが減少することを意味する。 0.80
This usually translates into models that are more resourceefficient in training, e g by requiring fewer parameters or fewer training samples. これは通常、パラメータの削減やトレーニングサンプルの削減など、トレーニングでよりリソース効率の高いモデルに変換される。 0.76
In our comparison of the EQC and the NEQC, we fix the number of training samples and compare the different models in terms of circuit depth and number of parameters to achieve a certain validation error and expect that the EQC will need fewer layers to achieve the same validation performance as the NEQC. EQCとNEQCの比較では、トレーニングサンプルの数を修正し、回路深度とパラメータの数で異なるモデルを比較して一定の検証誤差を達成するとともに、NEQCと同じ検証性能を達成するために、EQCがより少ないレイヤを必要とすることを期待する。 0.77
This comparison can be seen in fig. この比較は図で見ることができる。 0.75
5. In fig. 5. フィギュアで 0.35
5 a) and b), we show the training and validation performance of both ansatzes at depth one. 5 a) と b) 両アンサーゼの深度1でのトレーニングおよび検証性能を示す。 0.60
For instances with five cities, 10100Number of training instances1.01.11.21. oximation ratioEQCHWETEHWErand om10100Number of training instances1.01.11.21. oximation ratioEQCHWETEHWErand om10100Number of training instances1.001.251.5 01.752.002.252.502.7 53.00Approximation ratioEQCHWETEHWErand om10100Number of training instances1.001.251.5 01.752.002.252.502.7 53.00Approximation ratioEQCHWETEHWErand om 5つの都市の例です 10100 トレーニングインスタンス1. 51.71.8 近似比eqchwetehwerandom101 00 トレーニングインスタンス1. 61.71.8近似比eqchwetehwerandom101 00 トレーニングインスタンス1.001.251.501.752.00 2.252.502.753.00 近似比eqchwetehwerandom101 00 トレーニングインスタンス1.001.251.501.752.00 2.252.502.753.00 近似比eqchwetehwerandom 0.47
both ansatzes perform almost identically on the validation set, where the NEQC performs worse on a few validation instances. 両方の ansatze は検証セット上でほぼ同じ性能で動作し、いくつかの検証インスタンスではneqcがより良く動作する。
訳抜け防止モード: 両方のアンサーゼは検証セットでほぼ同じ動作をします NEQCは、いくつかのバリデーションインスタンスで悪化する。
As the instance size increases, the gap between EQC and NEQC becomes bigger. インスタンスサイズが大きくなると、eqcとneqcのギャップが大きくなる。 0.64
We see that even though the two ansatzes are structurally identical, the specific type of parametrizations we choose and the properties of both ansatzes that result from this make a noticeable difference in performance. 2つのアンサーゼは構造的に同一であるにもかかわらず、我々が選択する特定のタイプのパラメトリゼーションと、この結果生じる両方のアンサーゼの特性は、パフォーマンスに顕著な違いをもたらす。 0.72
While the EQC at depth one has only two parameters per layer regardless of instance size, the NEQC’s number of parameters per layer depends on the number of nodes and edges in the graph. 深さ1のEQCは、インスタンスサイズに関わらず、レイヤ毎に2つのパラメータしか持たないが、NEQCの1層のパラメータ数は、グラフ内のノード数とエッジ数に依存する。 0.74
Despite having much fewer parameters, the EQC still outperforms the NEQC on instances of all sizes. パラメータがはるかに少ないにもかかわらず、EQCはすべてのサイズのインスタンスでNEQCを上回っている。 0.62
Increasing the depth of the circuits also does not change this. 回路の深さを増加しても、これは変わらない。 0.76
In fig. 5 c) and フィギュアで 5 c) と 0.51
d) we see that at a depth of four, the EQC still beats the NEQC. d) 深さ4で、EQCがNEQCに勝っていることが分かる。 0.59
The latter’s validation performance even slightly decreases with more layers, which is likely due to the increased complexity of the optimization task, as the number of trainable parameters per layer is (n−1)n 2 + n, which for the 20-city instances means 840 trainable parameters at depth four (compared to 8 parameters in case of the EQC). レイヤ毎のトレーニング可能なパラメータの数は (n−1)n 2 + n であり、20のインスタンスでは、深さ4のトレーニング可能なパラメータが 840 である(EQCの場合は 8 のパラメータに比較)。
訳抜け防止モード: 後者のバリデーション性能は、より多くのレイヤでわずかに低下する。 最適化タスクの複雑さが増し 層ごとのトレーニング可能なパラメータの数が (n−1)n 2 + n であるように これは20のインスタンスに対して、深さ4のトレーニング可能なパラメータ840(EQCの場合の8パラメータと比較して)を意味する。
This shows that at a fraction of the number of trainable parameters, the EQC is competitive with its non-equivariant counterpart even though the underlying structure of both circuits is identical. これは、トレーニング可能なパラメータの数のごく一部において、EQCが両回路の基盤構造が同一であるにもかかわらず、同値でないパラメータと競合していることを示している。 0.65
Compared to the classical nearest-neighbor heuristic, both ansatzes perform well and beat it at all instance sizes, and both ansatzes are also below the approximation ratio upper bound given by the Christofides algorithm on all validation instances. 古典的最寄りのヒューリスティックと比較すると、両アンサットは全てのインスタンスサイズでうまく動作し、また両アンサットは全ての検証インスタンスのクリストフィデスアルゴリズムによって与えられる近似比の上界よりも小さい。 0.65
Next, we compare the EQC to ansatzes in which we introduce additional variational components that are completely unrelated to the training data structure, as described above. 次に、eqc と ansatzes を比較し、上記のようにトレーニングデータ構造とは全く無関係な付加的な変分成分を導入する。
訳抜け防止モード: 次に、EQCとアンサーゼを比較します。 上述したように、トレーニングデータ構造とは無関係な追加の変動成分を導入します。
We show results for the HWETE and the HWE ansatz in fig. フィグにおけるHWETEとHWEアンサッツの結果を示す。 0.63
6. To our own surprise, we did not manage to get satisfactory results with either of those two ansatzes, especially at larger instances, despite an intensive hyperparameter search. 6. 意外なことに、これらの2つのアンサーゼ、特に大きなケースでは、過度なハイパーパラメーターサーチにもかかわらず、満足な結果が得られなかったのです。 0.50
Even the HWETE, which is basically identical to the NEQC with additional trainable parameters in each layer, failed to show any significant performance. HWETEは基本的にNEQCと同じで、各層にトレーニング可能なパラメータを追加していたが、大きな性能は示さなかった。 0.70
To gauge how badly those two ansatzes perform, we also show results for an algorithm that selects a random tour for each validation instance in fig. また,これら2つのアンサーゼの動作を測るために,各検証インスタンスに対してランダムなツアーを選択するアルゴリズムの結果を示す。 0.75
6. In this figure, we show results for TSP instances with five and ten cities for both ansatzes with one and four layers, respectively. 6. この図では、tspインスタンスが5都市と10都市で、それぞれ1層と4層からなるansatzeで結果を示す。 0.54
Additionally, we show how the validation performance changes when the models are trained with either a training data set consisting of 10 or 100 instances, in the hopes of seeing improved performance as the size of the training set increases. さらに,モデルが10インスタンスあるいは100インスタンスからなるトレーニングデータセットでトレーニングされた場合,トレーニングセットのサイズが大きくなるにつれてパフォーマンスが向上することを期待して,検証性能がどう変化するかを示す。 0.88
We see that in neither configuration, the HWETE or HWE outperform the Christofides upper bound on all validation instances. どちらの構成でも、HWETEやHWEは、すべてのバリデーションインスタンスにおいてChristofidesの上限よりも優れています。 0.49
Additionally, in almost all cases those two ansatzes do not even outperform the random algorithm. さらに、ほとんどの場合、これらの2つのアンサーゼはランダムアルゴリズムよりも優れているわけではない。 0.56
This example shows that in a complex learning scenario, where the number of permutations of each input instance grows combinatorially with instance size and the number of states in the RL environment grows exponentially with the number of この例は、複雑な学習シナリオにおいて、各入力インスタンスの置換数がインスタンスサイズと組み合わせて増加し、RL環境の状態数が指数関数的に増加することを示す。 0.77
13 instances, a simple hardware-efficient ansatz will fail even when the data encoding part of the PQC is motivated by the problem data structure. 13 例えば、PQCのデータ符号化部が問題データ構造によって動機付けられても、単純なハードウェア効率のアンサッツは失敗する。 0.79
While increasing the size of the training set and/or the number of layers in the circuit seems to provide small advantages in some cases, it also leads to a decrease in performance in others. トレーニングセットのサイズと/または回路内のレイヤ数の増加は、いくつかのケースではわずかに利点があるように見えるが、他のケースではパフォーマンスが低下する。 0.68
On the other hand, the EQC is mostly agnostic to changes in the number of layers or the training data size. 一方、EQCは主にレイヤ数やトレーニングデータサイズの変化に依存しません。 0.47
Overall, we see that the closer the ansatz is to an equivariant configuration, the better it performs, and picking ansatzes that respect symmetries inherent to the problem at hand is the key to success in this graph-based learning task. 全体として、ansatzが等価な構成に近づくほど、パフォーマンスが向上し、問題に固有の対称性を尊重するアンサットを選択することが、このグラフベースの学習タスクの成功の鍵となります。 0.72
B. Solving the TSP with the QAOA B.QAOAによるTSPの解決 0.74
In section V A, we compared the performance of the EQC to a number of non-equivariant ansatzes and the classical nearest-neighbor heuristic. 第V節では,EQCの性能を,非同変アンサーゼおよび古典的近接ヒューリスティックと比較した。 0.65
We have also seen in section III that our ansatz is closely related to that of the QAOA. 第III節では、我々のアンザッツがQAOAと密接に関連していることも見てきた。 0.58
As the QAOA is arguably the most explored variational quantum optimization algorithm at the time of writing, and due to the structural similarity between the EQC and the QAOA’s ansatz, we also compare these two approaches on TSP instances with five cities. QAOAは書き込み時の最も検討された変分量子最適化アルゴリズムであり、EQCとQAOAのアンサッツの構造的類似性のため、これらの2つのアプローチをTSPインスタンスと5つの都市で比較する。 0.78
QAOA is implemented as a PQC by a Trotterization of Adiabatic Quantum Computation (AQC) [9]. QAOAは、AQC (Adiabatic Quantum Computation) [9] のトロッター化によってPQCとして実装される。 0.79
In general, for AQC, we consider a starting Hamiltonian H0, for which both the formulation and the ground state are well known, and a final Hamiltonian HP , that encodes the combinatorial optimization problem to be solved. 一般に、AQC に対して、定式化と基底状態の両方がよく知られた開始ハミルトニアン H0 と、組合せ最適化問題を符号化する最終ハミルトニアン HP を考える。 0.60
The system is prepared in the ground state of the Hamiltonian H0 and then it is evolved according to the time-dependent Hamiltonian: この系はハミルトニアン H0 の基底状態で準備され、その後時間依存のハミルトニアンに従って進化する。 0.62
H(t) := (1 − s(t))H0 + s(t)HP , H(t) := (1 − s(t))H0 + s(t)HP , 0.44
where s(t) is a real function called annealing schedule that satisfies the boundary conditions: s(0) = 0 and s(T ) = 1, with T the duration of the evolution. ここで、s(t) は境界条件を満たすアニーリングスケジュールと呼ばれる実関数であり、s(0) = 0 と s(t ) = 1 であり、t は進化の期間である。 0.75
To implement this as a quantum circuit we use the following approximation: これを量子回路として実装するには、以下の近似を用いる。 0.69
eA+B ≈(cid:16) eA+B > (cid:16) 0.33
(cid:17)r e (cid:17)r へえ 0.47
A r e a r e である。 0.54
B r , r → +∞, B r , r → +∞ である。 0.58
(19) which is knwon as the Trotter-Suzuki formula. (19) トローター・スズキ公式のクヌーンです。 0.43
By using this formula to approximate the evolution according to H(t) and by parameterizing time we obtain: この公式を用いて、H(t) に従って進化を近似し、パラメータ化時間を求める。 0.74
e−iβpH0e−iγpHP ··· e−iβ1H0 e−iγ1HP . e-iβpH0e-iγpHP ···・e-iβ1H0 e-iγ1HP。 0.18
(20) All of these matrices are unitary since the Hamiltonians in the argument of the exponential are all Hermitian. (20) 指数関数の議論におけるハミルトニアンはすべてエルミートであるので、これらの行列はすべてユニタリである。
訳抜け防止モード: (20) これらの行列はすべてユニタリなので 指数関数論のハミルトニアンはすべてエルミートである。
We define a parameter p (integer known as the depth, or level) of QAOA which has the same role as r in eq. eq において r と同じ役割を持つ qaoa のパラメータ p (深さまたはレベルとして知られる整数) を定義する。 0.78
(19). Increasing the depth p adds additional layers to the QAOA circuit, and thus more closely approximates the H(t) [9]. (19). 深さ p を増加させることで qaoa 回路に層を追加し、h(t) [9] をより密接に近似する。 0.59
In QAOA, all qubits are initialized to |+(cid:105)⊗n , which x . QAOA では、すべての量子ビットは |+(cid:105) =n に初期化される。 0.62
Alternating layers of Hp and H0 are added to the circuit (p times), 回路(p時間)にHpとH0の交互層を付加する。 0.74
is the ground state of H0 =(cid:80) H0 =(cid:80)の基底状態である 0.78
i σ(i) i σ(i) 0.43
14 on the results of the previous step. 14 前回のステップの結果についてです 0.51
In fig. 7 we show our results for five-city instances of the TSP. フィギュアで 7) tspの5都市における実測結果を示す。 0.41
The approximation ratio shown is derived by dividing the tour length of the best feasible solution, measured as the output of the trained QAOA circuit, by the optimal tour length of the respective instance. 前記近似比は、トレーニングされたQAOA回路の出力として測定された最良の実現可能な解のツアー長を各インスタンスの最適ツアー長で分割することによって導出される。 0.73
In addition, we compute results for two different p = 3 QAOA circuits: the first is trained in the procedure described above (where the parameters are trained for each instance). さらに, 2 つの異なる p = 3 個の QAOA 回路に対する結果を計算する。
訳抜け防止モード: さらに、2つの異なる p = 3 QAOA 回路に対する結果を計算する。 1つ目は、上記の手順(各インスタンスでパラメータがトレーニングされている)でトレーニングされる。
The second uses the parameters of the best QAOA circuit out of those for all instances evaluated at p = 3, following a concentration of parameters argument as presented in [49]. 第2の方法は,[49]に示すパラメータ引数の集中度に従って,p = 3 で評価されたすべてのインスタンスに対して,最適なqaoa回路のパラメータを使用する。 0.80
The second method is closer to what is done in a ML context, where one set of parameters is used to evaluate the performance on all validation samples. 第2のメソッドはMLコンテキストで行われていることに近いもので、すべての検証サンプルのパフォーマンスを評価するために1つのパラメータセットが使用される。 0.76
Due to the number of qubits required to formulate a QUBO for the TSP, we were not able to run QAOA for all TSP instances. TSPのQUBOの定式化に必要なキュービット数のため、すべてのTSPインスタンスに対してQAOAを実行することができなかった。 0.73
For example, an instance with six cities already requires 25 qubits5. 例えば、6つの都市では25 qubits5がすでに必要だ。 0.82
A different formulation of the QUBO problem presented in [50], that needs O(n log(n)) qubits, avoids this issue by modifying the circuit design. O(n log(n)) qubitsを必要とする[50]で示されるQUBO問題の異なる定式化は、回路設計を変更することによってこの問題を回避する。 0.80
However, this proposal increases the circuit depth considerably and is therefore ill-suited for the NISQ era. しかし、この提案は回路深度を大幅に向上させるため、NISQ時代には不適当である。 0.62
In fig. 7, we can see that finding a good set of parameters for QAOA to solve TSP is hard even for five-city instances. フィギュアで QAOA が TSP を解決するためのパラメータセットを見つけるのは,5 つのインスタンスであっても難しいことが分かる。 0.48
We note that the performance of QAOA improves with higher p, however, QAOA performance is still far from matching the approximation ratios obtained by EQC even for p = 3, which can be seen in fig. QAOAの性能は高いpで向上するが、p = 3 であっても、QAOA の性能は EQC が得られる近似比と一致しない。
訳抜け防止モード: qaoaの性能は、より高いpで向上します。 しかし qaoaのパフォーマンスは p = 3 においても eqc によって得られる近似比の一致は fig で見ることができる。
7 as a black dashed line. 7は黒の破線である。 0.79
Furthermore, we note that significant computational effort is required to obtain these results: methods like COBYLA are based on gradient descent, which requires us to evaluate the circuit many times until either convergence or the maximum number of iterations is reached. さらに、COBYLAのような手法は勾配勾配に基づいており、収束か最大反復回数に到達するまで回路を何度も評価する必要がある。
訳抜け防止モード: さらに留意すべき点は これらの結果を得るためには かなりの計算努力が必要です COBYLAのような手法は勾配降下に基づく。 コンバージェンスか最大イテレーション数に到達するまで 回路を何度も評価しなければなりません
We also note that due to the heuristic optimization of the QAOA parameters themselves, we are not guaranteed that the configuration of parameters is optimal, which may result in either insufficient iterations to converge or premature convergence to sub-optimal parameter values. また、qaoaパラメータ自体のヒューリスティックな最適化のため、パラメータの構成が最適であることは保証されておらず、結果として不十分なイテレーションが収束するか、あるいはサブ最適パラメータ値への早期収束をもたらす可能性があることに注意する。 0.65
In an attempt to mitigate this, we tested several optimizers (Adam, SPSA, BFGS and COBYLA) and used the best results, which were those found by COBYLA. これを軽減するために,いくつかのオプティマイザ(Adam,SPSA,BFGS,COBY LA)を試験し,COBYLAが検出した最良の結果を使用した。 0.76
We see that already on these small instances, the QAOA requires significantly deep circuits to achieve good results, that may be out of reach in a NISQ setting. これらの小さなインスタンスでは、QAOAは優れた結果を得るためにかなり深い回路を必要としており、NISQ設定では到達できない可能性がある。 0.68
The EQC on the other hand i) uses a number of qubits that scales linearly with the number of nodes of the input graph, and 一方のEQC i) 入力グラフのノード数と線形にスケールするいくつかの量子ビットを使用し、 0.59
ii) already shows good performance at depth one for instances with up to 20 cities. ii) 最大20都市までのインスタンスで、深度1でパフォーマンスが向上している。 0.73
FIG. 7: Approximation ratio of QAOA up to depth three. 第7図:深さ3までのqaoaの近似比。 0.65
Dashed black line denotes average final performance of the EQC at depth one during the last 100 iterations of training on the same instances. ダッシュブラックラインは、同じインスタンス上での最後の100回のトレーニングにおいて、EQCの平均的な最終パフォーマンスを深さ1で示す。 0.67
Last box shows the results for the best parameters found for one instance at p = 3 applied to all training instances, following a parameter concentration argument. 最後のボックスは、パラメータ集中度引数に従って、すべてのトレーニングインスタンスに適用されるp = 3のインスタンスで見つかった最良のパラメータの結果を示す。 0.77
The dotted, black line denotes the upper bound of the Christofides algorithm. 点在する黒い線は、クリストフィデスアルゴリズムの上限を表す。 0.55
parameterized by γ and β as defined in eq. eq で定義された γ と β でパラメータ化される。 0.71
(20). The values of γ and β are found by minimizing the expectation value of Hp, and thus approximate the optimal solution to the original combinatorial optimization problem. (20). γ と β の値は、hp の期待値を最小化し、元の組合せ最適化問題に対する最適解を近似することによって得られる。 0.62
When using QAOA, we do not solve the TSP directly, but a QUBO representation of this problem. QAOAを使用する場合、直接TSPを解くのではなく、この問題のQUBO表現を用いる。 0.72
This representation is well-known, and can be found in [47]: この表現はよく知られており [47] に見ることができる。 0.72
(cid:33)2 xi,t (cid:33)2 xi,t 0.42
+ xi,txj,t+1. + xi,txj,t+1。 0.65
(cid:88) (i,j)∈E (cid:88) (i,j)大E 0.37
+ N(cid:88) N(cid:88) + N(cid:88)N(cid:88) 0.41
t=1 t=1 t=1 である。 t=1 である。 0.31
(cid:88) (cid:33)2 (cid:88) (cid:33)2 0.39
i∈V (cid:32) 1 − N(cid:88) N(cid:88) (cid:88) ihtmlv (cid:32) 1 − N(cid:88) N(cid:88) (cid:88) 0.30
t=1 (i,j) /∈E t=1 である。 (i,j)/大E 0.34
t=1 xi,txj,t+1 + t=1 である。 xi,txj,t+1 + 0.38
εi,j W (cid:32) 1 −(cid:88) εi,j W (cid:32)1 −(cid:88) 0.45
i∈V xi,t + I-V xi,t + 0.35
Here, εi,j are the distances between two nodes i, j ∈ V and W := max(i,j)∈E εi,j. ここで εi,j は二つのノード i, j ∈ V と W := max(i,j)~E εi,j の間の距離である。 0.86
The variables xv,t are binary decision variables denoting whether node v is visited at step t. 変数 xv,t は、ステップ t でノード v が訪問されるかどうかを示す二項決定変数である。 0.69
We optimize the β and γ parameters for p = 1 by performing a uniform random search over the space [0, 2π]2, and selecting the best configuration found. 空間 [0, 2π]2 上で一様ランダム探索を行い、見つかった最良の構成を選択することで、p = 1 の β と γ のパラメータを最適化する。 0.88
For p = 2 and 3, we optimized the circuit parameters using Constrained Optimization BY Linear Approximation (COBYLA). p = 2 と 3 に対して、線形近似による制約最適化(COBYLA)を用いて回路パラメータを最適化した。 0.78
In addition, similar to [48], we employed a p-dependent initialization technique for the circuit parameters. また,[48]と同様,回路パラメータに対してp依存初期化手法を適用した。 0.78
Specifically, (p + 1)-depth QAOA circuit parameters were initialized with the optimal parameters from the p-depth circuit, as follows: 具体的には, (p + 1)-deepth QAOA回路パラメータを, p-deepth回路から最適パラメータで初期化した。 0.77
γ = (γ1, . . . , γp(cid:48), 0), β = (β1, . . . , βp(cid:48), 0). γ = (γ1, . . . , γp(cid:48), 0), β = (β1, . . . , βp(cid:48), 0). 0.49
This way we are allowing the parameter training procedure to start in a known acceptable state based このように、パラメータトレーニング手順を既知の許容状態ベースで開始できるようにしています。 0.69
5 We can fix the choice of the first city to be visited without loss of generality, requiring only (n − 1)2 variables to formulate the QUBO. 5) 一般性を失うことなく訪れる最初の都市の選択を修正でき、quboを定式化するために (n − 1)2 変数のみを必要とする。 0.80
1233, conc.p1. 41.51.6Approximation ratio 1233, conc.p1. 41.51.6近似比 0.12
VI. DISCUSSION After providing analytic insight on the expressivity of our ansatz, we have numerically investigated the performance of our EQC model on TSP instances with 5, 10, and 20 cities (corresponding to 5, 10, 20 qubits respectively), and compared them to other types of ansatzes that do not respect any graph symmetries. VI。 討論 ansatzの表現性に関する分析的考察を行った結果,5,10,20都市(それぞれ5,10,20量子ビットに対応)のtspインスタンスにおけるeqcモデルの性能を数値的に検討し,グラフ対称性を尊重しない他のタイプのアンサットと比較した。 0.60
To get a fair comparison, we designed PQCs that gradually break the equivariance property of the EQC and assessed their performance. 公平な比較を得るために、我々は、EQCの等値性を徐々に破壊し、その性能を評価するPQCを設計した。 0.61
We find that ansatzes that contain structures that are completely unrelated to the input data structure are extremely hard to train for this learning task where the size of the state space scales exponentially in the number of input nodes of the graph. 入力データ構造と完全に無関係な構造を含むansatzeは、グラフの入力ノード数で状態空間のサイズが指数関数的にスケールするこの学習タスクのために、非常に訓練が難しいことが分かりました。 0.81
Despite much effort and hyperparameter optimization, we did not manage to get satisfactory results with these ansatzes. 多大な努力とハイパーパラメータの最適化にもかかわらず、これらのアンサットで満足のいく結果を得ることはできなかった。 0.47
The EQC on the other hand works almost out-of-the box, and achieves good generalization performance with minimal hyperparameter tuning and relatively few trainable parameters. 一方、EQCはほとんどアウトオブザボックスで動作し、最小限のハイパーパラメータチューニングと比較的少ないトレーニング可能なパラメータで優れた一般化性能を実現する。 0.68
We have also compared using the EQC in a neural combinatorial optimization scheme with the QAOA, and find that even on TSP instances with only five cities the NCO approach significantly outperforms the QAOA. また,QAOAとニューラルネットワークの組合せ最適化スキームにおけるEQCの使用も比較した。また,5都市に限られるTSPインスタンスにおいても,NCOアプローチの方がQAOAを著しく上回ることがわかった。 0.71
In addition to training the QAOA parameters for every instance individually, we have also investigated the performance in light of known parameter concentration results that state that in some cases, parameters found on one instance perform well on average for other instances of the same problem. 各インスタンスのqaoaパラメータを個別にトレーニングすることに加えて、既知のパラメータ集中度の結果から、あるインスタンスで見つかったパラメータが、同じ問題の他のインスタンスで平均的によく機能することを示す性能についても調査した。 0.77
While this is true in the case of the TSP instances we investigate here as well, the overall performance is still worse than that of the EQC. 私たちがここで調査しているtspインスタンスの場合、これは事実ですが、全体的なパフォーマンスはeqcのものよりも悪くなります。 0.63
Comparing our algorithm to the QAOA is also interesting from a different perspective. アルゴリズムとQAOAを比較することも、異なる観点から興味深い。 0.65
In section III we have seen that our ansatz can be regarded as a special case of a QAOA-type ansatz, where instead of encoding a problem Hamiltonian we encode a graph instance directly, and include mixing terms only for a problem-dependent subset of qubits. 第3節では、我々のアンサッツはqaoa型アンサッツの特別な場合と見なすことができ、そこでは問題ハミルトニアンを符号化する代わりにグラフインスタンスを直接エンコードし、クビットの問題依存部分集合に対してのみ混合項を含む。 0.72
This lets us derive an exact formulation of the expectation values of our model at depth one from those of the QAOA given in [40]. これにより、[40] で与えられた QAOA の値から、深さ 1 でモデルの期待値の正確な定式化を導出できる。 0.71
For the QAOA, it is known that in the limit of infinite depth, it can find the ground state of the problem Hamiltonian and therefore the optimal solution to a given combinatorial optimization problem [9]. qaoa において、無限深さの極限において、問題ハミルトンの基底状態と与えられた組合せ最適化問題の最適解を見つけることが知られている [9]。 0.67
Additionally, it has been shown that even at low depth, the probability distributions generated by QAOA-type circuits are hard to sample from classically [51]. さらに,QAOA型回路が生成する確率分布は,低深さでも古典的に[51]のサンプリングが困難であることが示されている。 0.81
These results give a clear motivation of why using a quantum model in these settings can provide a potential advantage. これらの結果は、量子モデルをこれらの設定で使うことが潜在的な利点となる理由を明確に示している。 0.66
While our model is structurally almost identical to that of the QAOA, in our case the potential for advantage is less clear. 我々のモデルは構造的にはQAOAとほぼ同一であるが、我々の場合、利点の可能性が低い。 0.69
We saw in eq. (17) that at depth one, in each step the expectation value of each edge that we consider to be selected consists of eqで見た。 17) 深度1では,各ステップにおいて,選択されると考えられる各エッジの期待値が構成される 0.68
i) a term corresponding to the edge between the last added node and the candidate node, and 一 最後の追加ノードと候補ノードの間の端に相当する用語 0.57
ii) all outgoing edges from the candidate node. i) 候補ノードから全てのエッジを出力する。 0.81
So our model considers the one-step neighborhood of each candidate node at depth one. そこで本モデルは,各候補ノードの1ステップ近傍を深さ1で検討する。 0.61
In the case of the 15 TSP it is not clear whether this can provide a quantum advantage for the learning task as specified in section IV A. In terms of QAOA, it was shown that in order to find optimal solutions, the algorithm has to “see the whole graph” [52], meaning that all edges in the graph contribute to the expectation values used to minimize the energy. その場合 15 TSPは、この手法が第4節Aで規定された学習課題に量子的優位性を与えることができるかどうかを定めていない。QAOAの観点では、最適解を見つけるためには、アルゴリズムが「グラフ全体を見る」こと[52]、すなわち、グラフのすべてのエッジが、エネルギーを最小化するために使用される期待値に寄与することが示されている。 0.48
To alleviate this strong requirement on depth, a recursive version of the QAOA (RQAOA) was introduced in [53]. この深度に対する強い要求を軽減するため、[53]に再帰的なQAOA(RQAOA)が導入されました。 0.80
It works by iteratively merging edges in the problem graph based on their correlation, and thereby gradually reducing the problem to a smaller instance that can be solved efficiently by a classical algorithm, e g by brute-force search. 相関関係に基づいて問題グラフのエッジを反復的にマージすることで機能し、ブルートフォースサーチなど古典的アルゴリズムで効率的に解ける小さなインスタンスに徐々に問題を還元する。
訳抜け防止モード: それは、それらの相関に基づいて問題グラフのエッジを反復的にマージすることによって機能する。 徐々に問題を小さくし 従来のアルゴリズム、例えば brute - force search で効率的に解ける。
The authors of [53] show that the depth-one RQAOA outperforms QAOA with constant depth p, and that RQAOA achieves an approximation ratio of one for a family of Ising Hamiltonians. 53] の著者らは、深さ 1 の RQAOA が一定の深さ p で QAOA を上回り、RQAOA が Ising Hamiltonian の族に対する 1 の近似比を達成することを示した。 0.69
While the RQAOA at depth one can be considered a classical algorithm due to its efficient simulability, a subsequent work compared higher depth versions of RQAOA to the best known generic classical algorithm for graph coloring and showed that these deeper versions of RQAOA outperform the classical approach [54]. 深度でのRQAOAは、その効率的なシミュラビリティのために古典的アルゴリズムと見なすことができるが、その後の研究は、RQAOAのより深いバージョンが古典的アプローチよりも優れていることを示した。
訳抜け防止モード: RQAOAの深さは、その効率的なシミュラビリティのために古典的なアルゴリズムと見なすことができる。 その後の研究は、RQAOAのより深いバージョンをグラフ色付けのための最もよく知られた古典的アルゴリズムと比較した そして、これらのRQAOAのより深いバージョンが古典的なアプローチ [54 ] より優れていることを示した。
This suggests that there is a potential for advantage in this setting as well. これは、この設定にも利点があることを示唆している。 0.64
The node selection process performed by our algorithm with the EQC used as the ansatz is similar to RQAOA, where instead of merging edges, the mixer terms for nodes that have already been selected are turned off, therefore effectively turning expectation values of edges corresponding to unavailable nodes to zero. ansatzとして使用されるeqcでアルゴリズムによって実行されるノード選択プロセスはrqaoaと似ており、マージエッジの代わりに、既に選択されたノードのミキサー項をオフにすることで、使用できないノードに対応するエッジの期待値をゼロにする。 0.80
It is and interesting question whether this type of model can lead to a quantum advantage on the TSP problem that we study here, and we leave this for future work. この種のモデルが、私たちがここで研究しているTSP問題に量子的優位性をもたらすことができるかどうか、また、興味深い疑問である。 0.72
VII. CONCLUSIONS VII。 コンキュレーション 0.64
Inspired by classical geometric deep learning and in an effort to illustrate the importance of problemtailored ansatzes for QML, we have proposed an ansatz for learning on weighted graphs in this work. 古典的幾何学的深層学習に触発され,QMLにおける問題修正アンサーゼの重要性を説明すべく,本研究において重み付きグラフを学習するためのアンザッツを提案する。 0.73
This ansatz respects an important graph symmetry, namely equivariance under node permutations. このアンサッツは重要なグラフ対称性、すなわちノード置換の下での等分散を尊重する。 0.54
By designing our PQC such that it inherently respects this symmetry, we have encoded a problem-motivated bias into our model. この対称性を本質的に尊重するようにPQCを設計することで、問題動機バイアスをモデルにエンコードした。 0.69
A model that does not inherently respect this symmetry will treat each permutation of a training instance as a separate data point and thus has to learn good parameter settings for each individual permutation. この対称性を本質的に尊重しないモデルは、トレーニングインスタンスの各置換を別のデータポイントとして扱うため、個々の置換に対して適切なパラメータ設定を学ぶ必要がある。
訳抜け防止モード: この対称性を本質的に尊重しないモデルは、トレーニングインスタンスの各置換を別々のデータポイントとして扱う。 それぞれの順列のパラメータ設定を 学ばなければなりません
Our equivariant model on the other hand, “recognizes” a permutation of a graph instance and will therefore not need separate training data points to learn parameters for each possible permutation, of which there are combinatorially many. 一方で、同変モデルでは、グラフインスタンスの順列を“認識”するので、それぞれの可能な順列についてパラメータを学ぶために、個別のトレーニングデータポイントは必要ありません。
訳抜け防止モード: 一方、同変モデルでは、グラフインスタンスの置換を“認識”します。 それゆえ 個別の訓練データポイントは必要とせず 組合せ数が多い可能性のある各置換のパラメータを学習する。
Classically, it was proven that these types of models require fewer training data to generalize well than their unstructured counterparts [55]. 古典的には,これらのモデルでは,非構造化モデル [55] よりもトレーニングデータが少ないことが証明された。 0.76
It is an interesting question for future work whether these types of statements can also be made about quantum models. 将来の研究において、このようなステートメントが量子モデルにも適用できるかどうかは興味深い問題である。 0.70
Our results illustrate the need for QML ansatzes that are motivated by the training data structure. 本研究は,トレーニングデータ構造に動機づけられたqml ansatzesの必要性を示す。 0.68
We introduced such an ansatz for learning tasks on weighted graphs, however, more research is required to find suitable ansatzes for other types of data as well in order to make a near-term advantage in QML possible in the future. 重み付きグラフでタスクを学習するためのアンサッツを導入したが、将来qmlの短期的優位性を実現するためには、他の種類のデータに適したアンサットを見つけるための研究がさらに必要である。 0.70
Acknowledgements AS thanks Elies Gil-Fuster and Radoica Draskic for valuable discussions about geometric deep learning. 覚書 Elies Gil-Fuster氏とRadoica Draskic氏による幾何学的ディープラーニングに関する貴重な議論に感謝します。 0.47
AS, MC and SY are funded by the German Ministry for Education and Research (BMB+F) in the project QAI2-Q-KIS under grant 13N15587. AS、MC、SYは、13N15587の認可のもと、QAI2-Q-KISプロジェクトにおいて、ドイツ教育研究省(BMB+F)から資金提供を受けている。 0.58
VD is supported by the Dutch Research Council (NWO/OCW), as part of the Quantum Software Consortium programme (project number 024.003.037). VDは、Quantum Software Consortiumプログラム(プロジェクト番号024.003.037)の一部としてオランダ研究評議会(NWO/OCW)によって支援されている。 0.66
VD also acknowledges the support by the project NEASQC funded from the European Union’s Horizon 2020 research and innovation programme (grant agreement No 951821). vdはまた、euのhorizon 2020 research and innovation program(grant agreement no 951821)から資金提供を受けたプロジェクトneasqcの支援も認めている。 0.64
16 [1] Quentin Cappart, Didier Ch´etelat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veliˇckovi´c. 16 [1]クエンティン・キャップパート、ディディエ・チャエテラート、エリアス・ハリル、アンドレア・ロディ、クリストファー・モリス、ペタル・ヴェリョーヴィ。 0.43
Combinatorial optimization and reasoning with graph neural networks. グラフニューラルネットワークを用いた組合せ最適化と推論 0.82
arXiv preprint arXiv:2102.09544, 2021. arXiv preprint arXiv:2102.09544, 2021 0.40
[2] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. [2]ヨシュア・ベンジオ、アンドレア・ロディ、アントワーヌ・プロボスト。 0.59
Machine learning for combinatorial optimization: a methodological tour d’horizon. 組合せ最適化のための機械学習: 方法論ツアーd’horizon。 0.83
European Journal of Operational Research, 290(2):405–421, 2021. European Journal of Operational Research, 290(2):405-421, 2021 0.44
[3] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. [3] oriol vinyals,meire fortunato,navdeep jaitly。 0.30
Pointer networks. ポインタネットワーク。 0.68
arXiv preprint arXiv:1506.03134, 2015. arXiv preprint arXiv:1506.03134, 2015 0.40
[4] Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. [4]ハンジュン・ダイ、エリアス・B・ハリル、ユユ・チャン、ビストラ・ディカルキナ、ル・ソング。 0.50
Learning combinatorial optimization algorithms over graphs. グラフによる組合せ最適化アルゴリズムの学習。 0.77
arXiv preprint arXiv:1704.01665, 2017. arxiv プレプリント arxiv:1704.01665, 2017 0.42
[5] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, et al Chip placement with deep reinforcement learning. 5] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, et al Chip Placement with Deep reinforcement learning。
訳抜け防止モード: 5 ] アザリア・ミルホセイニ アンナ・ゴルディ ムスタファ・ヤズガン joe jiang, ebrahim songhori, shen wang, young - ジュン・リー eric johnson氏、omkar pathak氏、songmin bae氏、そして深層強化学習によるalチップ配置。
arXiv preprint arXiv:2004.10746, 2020. arxiv プレプリント arxiv:2004.10746, 2020 0.44
[6] Mohammadreza 6] モハンマドレザ 0.40
Oroojlooy, Lawrence V Snyder, and Martin Tak´aˇc. オルージュロイ、ローレンス5世スナイダー、マーティン・タック。 0.45
Reinforcement learning for solving the vehicle routing problem. 車両経路問題を解決するための強化学習 0.81
arXiv preprint arXiv:1802.04240, 2018. arXiv preprint arXiv:1802.04240, 2018 0.39
Nazari, Afshin [7] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veliˇckovi´c. なざり アフシン 7]マイケル・m・ブロンスタイン、ジョアン・ブルーナ、タコ・コーエン、ペタル・ヴェリシコヴィ(petar velisckovi)。 0.35
Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. 幾何学的ディープラーニング:グリッド、グループ、グラフ、測地線、ゲージ。 0.69
arXiv preprint arXiv:2104.13478, 2021. arXiv preprint arXiv:2104.13478, 2021 0.40
[8] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al Variational quantum algorithms. 8]marco cerezo、andrew arrasmith、ryan babbush、simon c benjamin、suguru endo、keisuke fujii、jarrod r mcclean、kosuke mitarai、xiao yuan、lukasz cincio、al variational quantum algorithms。
訳抜け防止モード: マルコ・セレゾ アンドリュー・アラスミス ライアン・バブブッシュ simon c benjamin, suguru endo, keisuke fujii, jarrod r mcclean, kosuke mitarai, xiao yuan, lukasz cincio, et al variational quantum algorithms など。
Nature Reviews Physics, 3(9):625–644, 2021. Nature Reviews Physics, 3(9):625–644, 2021。 0.46
[9] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 9]エドワード・ファリー、ジェフリー・ゴールドストーン、サム・グートマン 0.53
A quantum approximate optimization algorithm. 量子近似最適化アルゴリズム。 0.73
arXiv preprint arXiv:1411.4028, 2014. arxiv プレプリント arxiv:1411.4028, 2014 0.43
[10] Tavis Bennett, Edric Matwiejew, Sam Marsh, and Jingbo B Wang. 10]Tavis Bennett、Edric Matwiejew、Sam Marsh、Jingbo B Wang。 0.67
Quantum walk-based vehicle routing optimisation. 量子ウォークに基づく車両ルーティング最適化 0.69
Frontiers in Physics, page 692, 2021. 物理学のフロンティア』692ページ、2021年。 0.76
[11] Harper R Grimsley, Sophia E Economou, Edwin Barnes, and Nicholas J Mayhall. Harper R Grimsley氏、Sophia E Economou氏、Edwin Barnes氏、Nicholas J Mayhall氏。 0.69
Adapt-vqe: An exact variational algorithm for fermionic simulations on a quantum computer. Adapt-vqe: 量子コンピュータ上のフェルミオンシミュレーションのための正確な変分アルゴリズム。 0.81
arXiv preprint arXiv:1812.11173, 2018. arXiv preprint arXiv:1812.11173, 2018 0.39
[12] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Al´an Aspuru-Guzik, and Jeremy L O’brien. Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Al ́an Aspuru-Guzik, Jeremy L O’brien
訳抜け防止モード: 12] アルベルト・ペルッツォ ジャロッド・マクリーン ピーター・シャドボルト 男-ホン・ユン、シャオ-チー・周、ピーター・j・ラブ グジク(guzik)とジェレミー・l・オブライエン(jeremy l o'brien)。
A variational eigenvalue solver on a photonic quantum processor. フォトニック量子プロセッサにおける変動固有値解法 0.64
Nature communications, 5(1):1–7, 2014. 自然通信 5(1):1-7 2014年。 0.85
[13] Abhinav Kandala, Antonio Mezzacapo, Kristan [13]Abhinav Kandala,Antonio Mezzacapo,Kristan 0.38
Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. Temme、Maika Takita、Markus Brink、Jerry M Chow、Jay M Gambetta。 0.31
Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. 小型分子と量子磁石のハードウェア効率可変量子固有解法 0.82
Nature, 549(7671):242–246, 2017. 549(7671):242-246、2017年。 0.61
[14] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. 14]マルチェロ・ベネデッティ、エリカ・ロイド、ステファン・サック、マティア・フィオレンティーニ 0.36
Parameterized quantum circuits as machine learning models. 機械学習モデルとしての量子回路のパラメータ化。 0.68
Quantum Science and Technology, 4(4):043001, 2019. 量子科学と技術, 4(4):043001, 2019。 0.83
[15] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Jarrod R McClean氏、Sergio Boixo氏、Vadim N Smelyanskiy氏、Ryan Babbush氏、Hartmut Neven氏。 0.35
Barren plateaus in quantum neural network training landscapes. 量子ニューラルネットワークトレーニングランドスケープにおけるバレンプラトー 0.70
Nature communications, 9(1):1–6, 2018. ナチュラル・コミュニケーションズ、2018年1月9日:1-6日。 0.48
[16] Andrew Arrasmith, M Cerezo, Piotr Czarnik, Lukasz Cincio, and Patrick J Coles. 16] andrew arrasmith、m cerezo、piotr czarnik、lukasz cincio、patrick j coles。 0.47
Effect of barren plateaus on gradient-free optimization. 勾配なし最適化におけるバレン高原の影響 0.72
Quantum, 5:558, 2021. 量子 5:558, 2021 0.37
[17] Carlos Ortiz Marrero, M´aria Kieferov´a, and Nathan Wiebe. 17]carlos ortiz marrero、m ́aria kieferov ́a、nathan wiebe。 0.61
Entanglement-induced barren plateaus. 絡み合いによる不毛高原。 0.38
PRX Quantum, 2(4):040316, 2021. PRX Quantum, 2(4):040316, 2021。 0.44
[18] Patrick van der Smagt and Gerd Hirzinger. 18]Patrick van der SmagtとGerd Hirzinger。 0.34
Why feedforward networks are in a bad shape. なぜフィードフォワードネットワークは悪い形をしているのか。 0.61
In International Conference on Artificial Neural Networks, pages 159– 164. ニューラルネットワークに関する国際会議 (international conference on artificial neural networks) 159-164頁。 0.58
Springer, 1998. 1998年、スプリンガー。 0.60
[19] Code this https://github.com/a skolik/eqc for nco. 【19】コード https://github.com/a skolik/eqc for nco 0.54
used in work [20] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin ˇZ´ıdek, Anna Potapenko, et al Highly accurate protein structure prediction with alphafold. 使用 イン 仕事 20]john jumper、richard evans、alexander pritzel、tim green、michael figurnov、olaf ronneberger、kathryn tunyasuvunakool、russ bates、augustin sz ́ıdek、anna potapenko、そしてal alのαfoldによる高精度なタンパク質構造予測 0.60
Nature, 596(7873):583– 589, 2021. 自然数 596(7873):583–589, 2021。 0.76
[21] Kathryn Tunyasuvunakool, Jonas Adler, Zachary Wu, Tim Green, Michal Zielinski, Augustin ˇZ´ıdek, Alex Bridgland, Andrew Cowie, Clemens Meyer, Agata Laydon, et al Highly accurate protein structure prediction for the human proteome. [21]Kathryn Tunyasuvunakool,Jona s Adler,Zachary Wu,Tim Green,Michal Zielinski,Augustin,Z ́ıdek,Alex Bridgland,Andrew Cowie,Clemens Meyer,Agata Laydonらによるヒトプロテオームの高精度タンパク質構造予測 0.75
Nature, 596(7873):590–596, 2021. 自然数 596(7873):590–596, 2021。 0.70
[22] Yann LeCun, Yoshua Bengio, et al 22]yann lecun, yoshua bengio, et al 0.32
Convolutional networks for images, speech, and time series. 画像、音声、時系列の畳み込みネットワーク。 0.53
The handbook of brain theory and neural networks, 3361(10):1995, 1995. the handbook of brain theory and neural networks, 3361(10): 1995年、1995年。 0.94
[23] Robin M Schmidt. ロビン・シュミット(Robin M Schmidt)。 0.58
Recurrent neural networks (rnns): A gentle introduction and overview. リカレントニューラルネットワーク(rnns): 穏やかな紹介と概要。 0.68
arXiv preprint arXiv:1912.05911, 2019. arXiv preprint arXiv:1912.05911, 2019 0.40
[24] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. [24] 宗武、シルイ・パン、フェンウェン・チェン、グードン・ロング、チェンキ・チャン、ス・ユ・フィリップ
訳抜け防止モード: ][24] 宗山武, しるいパン, フェンウェンチェン, guodong long、chenqi zhang、s yu philip。
A comprehensive survey on graph neural networks. グラフニューラルネットワークに関する総合的な調査 0.73
IEEE transactions on neural networks and learning systems, 32(1):4–24, 2020. IEEEはニューラルネットワークと学習システムに関するトランザクション、32(1):4–24, 2020。 0.79
[25] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 25] 江周, ガンク・クイ, シェンディン・フ, ジンジャン・ジン, チェン・ヤン, ジユアン・リ, ビョン・ワン, チャン・チョン・リ, マオソン・サン
訳抜け防止モード: [25 ]慈恵周,ガンクキュイ,シグディングフー, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang チャンチェン・リ(Changcheng Li)とマオソン・サン(Maosong Sun)。
Graph neural net- グラフニューラルネット- 0.78
works: A review of methods and applications. works: メソッドとアプリケーションのレビュー。 0.63
AI Open, 1:57–81, 2020. オープン1:57-81、2020。 0.66
[26] Elman Mansimov, Omar Mahmood, Seokho Kang, and Kyunghyun Cho. [26]エルマン・マンシモフ、オマール・マフムード、ソクホ・カン、ユングヒョン・チョー。 0.50
Molecular geometry prediction using a deep generative graph neural network. 深部生成グラフニューラルネットワークを用いた分子幾何学的予測 0.83
Scientific reports, 9(1):1–13, 2019. 科学誌 9(1):1–13, 2019。 0.42
[27] Jianwu Long et al A graph neural network for superpixel image classification. 27] jianwu long et al 超ピクセル画像分類のためのグラフニューラルネットワーク。 0.78
In Journal of Physics: Conference Series, volume 1871, page 012071. journal of physics: conference series, volume 1871, page 012071 を参照。 0.41
IOP Publishing, 2021. IOP出版、2021年。 0.78
[28] Iris Cong, Soonwon Choi, and Mikhail D Lukin. 28] アイリス・コン、スンウォン・チョイ、ミハイル・ド・ルキン 0.41
Quantum convolutional neural networks. 量子畳み込みニューラルネットワーク。 0.71
Nature Physics, 15(12):1273–1278, 2019. 自然物理学、15(12):1273-1278、2019。 0.71
[29] Guillaume Verdon, Trevor McCourt, Enxhell Luzhnica, Vikash Singh, Stefan Leichenauer, and Jack Hidary. 29] ギヨーム・ヴァードン、トレヴァー・マクコート、エンクセル・ルジニカ、ヴィカシュ・シン、ステファン・ライヒナウアー、ジャック・ヒダリー 0.44
Quantum graph neural networks. 量子グラフニューラルネットワーク。 0.72
arXiv preprint arXiv:1909.12264, 2019. arXiv preprint arXiv:1909.12264, 2019 0.41
[30] Louis-Paul Henry, Slimane Thabet, Constantin Dalyac, and Lo¨ıc Henriet. 30]ルイ=ポール・ヘンリー、スリム・サベット、コンスタンティン・ダリャック、ロ・シック・ヘンリエト。 0.59
Quantum evolution kernel: Machine learning on graphs with programmable arrays of qubits. quantum evolution kernel: 量子ビットの配列をプログラム可能なグラフ上の機械学習。 0.79
Physical Review A, 104(3):032416, 2021. 物理書評 A, 104(3):032416, 2021。 0.75
[31] Jin Zheng, Qing Gao, and Yanxuan L¨u. [31]ジン・ジン、清・ガオ、ヤンジュアン・l・ジュ。 0.49
Quantum graph convolutional neural networks. 量子グラフ畳み込みニューラルネットワーク。 0.69
In 2021 40th Chinese Control Conference (CCC), pages 6335– 6340. 2021年、第40回中国制御会議(ccc)、6335-6340頁。 0.64
IEEE, 2021. IEEE、2021年。 0.81
[32] Yanhu Chen, Cen Wang, Hongxiang Guo, et al Novel architecture of parameterized quantum circuit for graph convolutional network. [32]Yanhu Chen,Cen Wang,Hongxiang Guo,その他グラフ畳み込みネットワークのためのパラメータ化量子回路の新しいアーキテクチャ。 0.80
arXiv preprint arXiv:2203.03251, 2022. arXiv preprint arXiv:2203.03251, 2022 0.40
[33] P´eter Mernyei, Konstantinos Meichanetzidis, and ˙Ismail ˙Ilkan Ceylan. [33]P ́eter Mernyei, Konstantinos Meichanetzidis, およびIsmail, Ilkan Ceylan。 0.87
Equivariant quantum graph circuits. arXiv preprint arXiv:2112.05261, 2021. 等変量子グラフ回路 arXiv preprint arXiv:2112.05261, 2021 0.55
[34] Mart´ın Larocca, Fr´ed´eric Sauvage, Faris M. Sbahi, Guillaume Verdon, Patrick J. Coles, and M. Cerezo. マルト・ラロッカ、Fr ed ́eric Sauvage、Faris M. Sbahi、Guillaume Verdon、Patrick J. Coles、M. Cerezo。
訳抜け防止モード: マルティン・ラロッカ, Fr ́ed ́eric Sauvage, Faris M. Sbahi, Guillaume Verdon、Patrick J. Coles、M. Cerezo。
Group-invariant quantum machine learning. グループ不変量子機械学習。 0.82
arXiv preprint arXiv:2205.02261, 2022. arXiv preprint arXiv:2205.02261, 2022 0.40
[35] Richard S Sutton and Andrew G Barto. 35] リチャード・s・サットンと アンドリュー・g・バート 0.74
Reinforce- ment learning: An introduction. 補強 メンタラーニング: 入門。 0.31
MIT press, 2018. MIT出版、2018年。 0.71
[36] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al Human-level control through deep reinforcement learning. 36] volodymyr mnih, koray kavukcuoglu, david silver, andrei a rusu, joel veness, marc g bellemare, alex graves, martin riedmiller, andreas k fidjeland, georg ostrovski, et al human-level control through deep reinforcement learning
訳抜け防止モード: 36]volodymyr mnih, koray kavukcuoglu, david silver。 アンドレイ・ア・ルース ジョエル・ヴェニス マルク・g・ベネマレ アレックス・グレイヴス martin riedmiller, andreas k fidjeland, georg ostrovski, et al human - 深層強化学習によるレベル制御。
nature, 518(7540):529– 533, 2015. 自然, 518(7540): 529– 533, 2015 0.84
[37] Samuel Yen-Chi Chen, Chao-Han Huck Yang, Jun Qi, Pin-Yu Chen, Xiaoli Ma, and Hsi-Sheng Goan. [37]Samuel Yen-Chi Chen、Chao-Han Huck Yang、Jun Qi、Pin-Yu Chen、Xiaoli Ma、Hsi-Sheng Goan。
訳抜け防止モード: [37 ]Samuel Yen-Chi Chen,Chao-Han Huck Yang, Jun Qi, Pin - Yu Chen, Xiaoli Ma, シェン・ゴアン(Sheng Goan)。
Variational quantum circuits for deep reinforcement learning. 深層強化学習のための変分量子回路 0.80
IEEE Access, 8:141007–141024, 2020. IEEE Access, 8:141007–141024, 2020。 0.38
[38] Owen Lockwood and Mei Si. [38]オーウェン・ロックウッドとマイ・シー。 0.58
Reinforcement learning with quantum variational circuit. 量子変分回路を用いた強化学習 0.83
In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 16, pages 245–251, 2020. aaai conference on artificial intelligence and interactive digital entertainment』第16巻、第245-251頁、2020年。 0.65
[39] Andrea Skolik, Sofiene Jerbi, and Vedran Dunjko. 39] Andrea Skolik, Sofiene Jerbi, Vedran Dunjko。 0.32
Quantum agents in the gym: a variational quantum algorithm for deep q-learning. ジムにおける量子エージェント:深層q学習のための変分量子アルゴリズム。 0.83
arXiv preprint arXiv:2103.15084, 2021. arXiv preprint arXiv:2103.15084, 2021 0.40
[40] Asier Ozaeta, Wim van Dam, and Peter L McMahon. [40]Asier Ozaeta、Wim van Dam、Peter L McMahon。 0.31
Expectation values from the single-layer quantum approximate optimization algorithm on ising problems. イジング問題に対する単層量子近似最適化アルゴリズムからの期待値 0.88
arXiv preprint arXiv:2012.03421, 2020. arxiv プレプリント arxiv:2012.03421, 2020 0.42
[41] Mehryar Mohri. He41] Mehryar Mohri 0.25
Foundations of machine learning. https://cs.nyu.edu/ mohri/ml16/sol2.pdf, 2016. 機械学習の基礎。 https://cs.nyu.edu/ mohri/ml16/sol2.pdf、2016年。 0.53
[42] Gilbert H Harman, Sanjeev R Kulkarni, and Hariharan Narayanan. ギルバート・ハルマン(Gilbert H Harman)、サンジェフ・ル・クルカルニ(Sanjeev R Kulkarni)、ハリハラン・ナラヤナン(Hariharan Narayanan)。 0.48
sin(ωx) can approximate almost every finite set of samples. sin(ωx) はほとんど全ての有限個のサンプルを近似することができる。 0.68
Constructive Approximation, 42(2):303–311, 2015. 構成近似 42(2):303–311, 2015 0.79
17 [43] Seth Lloyd. 17 [43] セス・ロイド 0.49
tion is computationally universal. tionは計算的に普遍的です。 0.56
arXiv:1812.11075, 2018. arxiv:1812.11075、2018年。 0.34
Quantum approximate optimizaarXiv preprint 量子近似オプティミザーXivプレプリント 0.61
[44] Mauro ES Morales, Jacob D Biamonte, and Zolt´an Zimbor´as. [44] Mauro ES Morales, Jacob D Biamonte, Zolt ́an Zimbor ́as. 0.48
On the universality of the quantum approximate optimization algorithm. 量子近似最適化アルゴリズムの普遍性について 0.81
Quantum Information Processing, 19(9):1–26, 2020. 量子情報処理, 19(9):1–26, 2020 0.90
[45] Python-tsp https://github.com/fillipe-gsm/python- [45] Python-tsp https://github.com/f illipe-gsm/python 0.23
tsp. [46] Nicos Christofides. tsp。 ニコス・クリストフィデス(Nicos Christofides)。 0.50
Worst-case analysis of a new heuristic for the travelling salesman problem. 旅行セールスマン問題に対する新しいヒューリスティックの最悪のケース分析 0.61
Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, 1976. 1976年、カーネギー・メロン大学ピッツバーグ・パ・マネジメント・サイエンス・リサーチ・グループを設立。 0.46
[47] Andrew Lucas. アンドリュー・ルーカス(Andrew Lucas)。 0.64
Ising formulations of many np prob- 多数のnpプロブのイジング製剤- 0.69
lems. Frontiers in physics, 2:5, 2014. レム 物理学のフロンティア、2014年2:5。 0.44
[48] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. [48]Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, Mikhail D Lukin。 0.40
Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. 量子近似最適化アルゴリズム: 短期デバイスにおける性能、機構、実装。 0.80
Physical Review X, 11(2):021067, 2020. フィジカル・レビューX, 11(2):021067, 2020。 0.79
[49] Fernando G. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. [49] フェルナンド・g・ブランダオ、マイケル・ブロートン、エドワード・ファリー、サム・グットマン、ハートムート・ネブン 0.60
For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical arXiv preprint arXiv:1812.04170, 2018. 固定制御パラメータでは、量子近似最適化アルゴリズムの目的関数値は、典型的なarxivプレプリントarxiv:1812.04170, 2018に集中する。 0.63
instances. [50] Adam Glos, Alexandra Krawiec, and Zolt´an Zimbor´as. 例 [50]Adam Glos、Alexandra Krawiec、Zolt ́an Zimbor ́as。 0.30
Space-efficient binary optimization for variational computing. 変分計算のための空間効率のよいバイナリ最適化 0.62
arXiv preprint arXiv:2009.07309, 2020. arxiv プレプリント arxiv:2009.07309, 2020 0.44
[51] Edward Farhi and Aram W Harrow. エドワード・ファリーとAram W Harrow。 0.48
Quantum supremacy through the quantum approximate optimization algorithm. 量子近似最適化アルゴリズムによる量子超越性 0.82
arXiv preprint arXiv:1602.07674, 2016. arXiv preprint arXiv:1602.07674, 2016 0.40
[52] Edward Farhi, David Gamarnik, and Sam Gutmann. 52]エドワード・ファリー、デイヴィッド・ガマルニク、サム・グートマン 0.47
The quantum approximate optimization algorithm needs to see the whole graph: A typical case. 量子近似最適化アルゴリズムは、グラフ全体を見る必要がある:典型的な場合。 0.85
arXiv preprint arXiv:2004.09002, 2020. arxiv プレプリント arxiv:2004.09002, 2020 0.42
[53] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. 53] セルゲイ・ブラヴィイ、アレクサンドル・クリッシュ、ロバート・コーニグ、ユージーン・タン 0.55
Obstacles to variational quantum optimization from symmetry protection. 対称性保護からの変分量子最適化への障害 0.81
Physical review letters, 125(26):260505, 2020. 物理的レビューレター125(26):260505, 2020。 0.75
[54] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. 54] セルゲイ・ブラヴィイ、アレクサンドル・クリッシュ、ロバート・コーニグ、ユージーン・タン 0.54
Hybrid quantum-classical algorithms for approximate graph coloring. 近似グラフ彩色のためのハイブリッド量子古典アルゴリズム 0.80
Quantum, 6:678, 2022. 量子 6:678, 2022。 0.86
[55] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. [55]Song Mei、Theodor Misiakiewicz、Andrea Montanari。 0.32
Learning with invariances in random features and kernel models. ランダム特徴とカーネルモデルにおける不変性による学習。 0.73
In Conference on Learning Theory, pages 3351–3418. 学習理論に関する会議』3351-3418頁。 0.79
PMLR, 2021. PMLR、2021年。 0.80
Appendix A: Proof of equivariance of ansatz Appendix A: Ansatzの等価性の証明 0.71
Proof of theorem 1. First, we show that one layer of the ansatz is equivariant under permutation of graph vertices. 定理 1 の証明。 まず、アンサッツの1つの層がグラフ頂点の置換の下で同値であることを示す。 0.60
Our ansatz is initialized in the uniform superposition, which is permutation invariant by definition, so we only have to show that the unitaries each layer in the ansatz is equivariant. 我々のアンサッツは一様重ね合わせで初期化され、これは定義により置換不変であるので、アンサッツの各層が同値であることを示すのみである。 0.59
Each layer consists of two terms: UN (α, βj) and UG(E, γj). 各層は、UN (α, βj) と UG(E, γj) の2つの項からなる。 0.82
We need to show that both of these fulfill the equivariance property. これら両方が等分散性を満たすことを示す必要がある。 0.63
The first term contains only single-qubit operations, where each operation is defined w.r.t. vertices in G. For an arbitrary quantum state |ψ(cid:105) defined on a register of n qubits, a permutation of qubits 第一項は1量子ビット演算のみを含み、各演算は g において w.r.t. 頂点を定義する。 任意の量子状態 |ψ(cid:105) に対して n 量子ビットのレジスタ、すなわち qubit の置換で定義される。
訳抜け防止モード: 最初の項は、n 量子ビットのレジスタ上で定義された任意の量子状態 |ψ(cid:105 ) に対して、各演算は g において w.r.t で定義される。 qubits (複数形 qubits)
corresponds to applying a series of SWAP-gates on those qubits. これらのキュービットに一連のSWAPゲートを適用することに対応する。 0.53
The SWAP operation leaves the individual quantum states unchanged, and merely reassigns them to a new position in the register, therefore fulfilling the above equivariance property. SWAP の演算は個々の量子状態は変化せず、レジスタ内の新しい位置に再割り当てするだけで、したがって上記の等値性を満たす。 0.72
The second term UG consists of two-qubit ZZ-operators, each weighted by a trainable parameter γj and an edge weight εij. 第2項のUGは2量子ZZ演算子で構成され、それぞれがトレーニング可能なパラメータ γj とエッジウェイト εij で重み付けされる。 0.61
ZZ-operators are diagonal and therefore commute, so the order in which they are executed does not matter. zzオペレータは対角であり、したがって通勤するので、実行される順序は重要ではない。 0.66
In addition, the assignment of edge weights to the given ZiZj is determined by the adjacency matrix A of the graph, and therefore a permutation on the adjacency matrix directly translates to a re-assignment of edge weights to their corresponding ZiZj according to the permuted adjacency matrix, which makes the second term equivariant as well. さらに、与えられた zizj への辺重みの割り当ては、グラフの隣接行列 a によって決定され、したがって、隣接行列上の置換は、置換された隣接行列に従って対応する zizj への辺重みの再割り当てに直接変換され、2番目の項が同変となる。 0.67
Additionally, the permutation invariance of the trainable parameters is guaranteed by using one shared parameter for each ZZ-term or X-rotation in each layer. さらに、各層におけるZZ終端またはX回転毎に1つの共有パラメータを用いて、トレーニング可能なパラメータの置換不変性を保証する。 0.67
Note that parameters not being tied to specific edge weights is necessary, because otherwise trainable parameters would be assigned to different edge weights depending on the specific graph permutation, which would break equivariance. 訓練可能なパラメータは特定のグラフの置換によって異なるエッジ重みに割り当てられるため、特定のエッジ重みに縛られないパラメータが必要であることに注意されたい。 0.76
Now that we have shown that a single layer in our ansatz is equivariant under permutation of vertices, it remains to show that the composition of multiple layers is equivariant as well. アンザッツの1つの層が頂点の置換の下で同変であることが証明された今、複数の層の組成も同変であることは明らかではない。 0.61
This easily follows from the above, as we have already shown that the permutation of the single-qubit operators corresponding to vertices is akin to a SWAP operation on a quantum state |ψ(cid:105), that itself is permutation equivariant. これは、頂点に対応する単一量子ビット作用素の置換が、それ自身が置換同変である量子状態 |\ (cid:105) 上の SWAP 演算に類似していることが既に示されているように、上記のことから簡単に従うことができる。 0.60
In particular, this quantum state can be the state given by a previous layer of the ansatz. 特に、この量子状態は、アンサッツの前の層によって与えられる状態である。 0.60
The equivariance of multiple executions of the two-qubit operations in the ansatz then also follows directly from the above. アンサッツにおける2量子ビット演算の複数の実行の同分散もまた、上記のものから直接従う。 0.61
Note that the above is not true for arbitrary initial states of the circuit, but only for those that satisfy the equivariance property as well. 上記は、回路の任意の初期状態についてではなく、同値性を満たす状態に対してのみ成り立つことに注意されたい。 0.63
Any non-equivariant part in the ansatz will cause the whole ansatz to be non-equivariant. アンサッツの任意の非同値な部分により、アンサッツ全体が非同値になる。 0.36
In the main text, we have briefly discussed scenarios in which each node in the graph corresponds to multiple qubits in the ansatz. メインテキストでは、グラフの各ノードがアンサッツの複数のキュービットに対応するというシナリオを簡潔に論じている。 0.68
The above proof holds for the one qubit case, and whether an ansatz with multiple qubits per node will still be equivariant depends on the chosen mapping of node and edge features. 上の証明は1つの量子ビットの場合であり、ノードごとに複数の量子ビットを持つアンサッツが同値であるかどうかは、ノードとエッジの特徴の選択されたマッピングに依存する。 0.62
A trivial example where the above holds, is when multiple node features are encoded via single-qubit rotations on each additional qubit, and edge features are still encoded in form of commuting two-qubit gates as above. 上記のような自明な例は、追加のキュービットごとに複数のノード特徴が単一キュービット回転によって符号化され、エッジ特徴が上記のように2キュービットゲートを交換する形で符号化されるときである。 0.67
Appendix B: Proof that ansatz can generate Appendix B: ansatzが生成できる証明 0.76
optimal tours for rationally independent set of 合理的に独立な集合の最適ツアー 0.75
edge weights In this section, we show how the fact that the sine function can approximate an arbitrary set of rationally independent values {x1, . . . , xn} with labels エッジウェイト 本節では、正弦関数がラベル付き有理独立値 {x1, . . . . , xn} の任意の集合を近似できるという事実を示す。 0.61
18 yi ∈ [−1, 1] can be used prove that our ansatz at depth one can construct the optimal tour for a graph with edge weights that are rationally independent. 18 yi ∈ [−1, 1] は、深さでの ansatz が有理独立な辺重みを持つグラフの最適巡回を構築することができることを証明できる。 0.71
Theorem 4 (Ansatz can generate optimal tours for rationally independent edge weights). Theorem 4 (Ansatzは合理的に独立したエッジウェイトのための最適なツアーを生成することができる)。 0.54
There exists a setting (β, γ)∗ for each graph instance of the symmetric TSP such that the ansatz at depth one described in section III will produce the optimal tour T ∗ with the node selection process described in definition 2, given that the edge weights εij of the graph are rationally independent and εijγ (cid:54)= π 対称 TSP の各グラフインスタンスに対して (β, γ)∗ が存在し、そのグラフのエッジウェイト εij が合理的に独立であり εijγ (cid:54) = π が成立すると、セクションIII で記述された深度でのアンザッツが定義 2 で記述されたノード選択プロセスで最適なツアー T ∗ を生成する。 0.80
4 + nπ ∀ n ∈ Z. 4 + nπ , n ∈ z である。 0.79
Proof. As known from [42], we can find a parameter ω such that we can approximate an arbitrary labeling in [−1, 1] for our rationally independent edge weights with the sine function. 証明。 42] から知られているように、[−1, 1] の任意のラベル付けを正弦関数で有理独立な辺重みに対して近似できるようなパラメータ ω を見つけることができる。 0.68
Given that this labeling exists, we now show how to use this labeling to generate the optimal tour with the EQC at depth one. このラベリングが存在することを考慮し、このラベリングを用いてEQCによる最適なツアーを深度1で生成する方法を示す。 0.56
For p = 1, we can compute the analytic form of the expectation values of our circuit as defined in eq. p = 1 の場合、eq で定義される回路の期待値の解析形式を計算することができる。 0.76
(13) and eq. (13)およびeq。 0.77
(14) as the following, by a similar derivation as in [40], (14)[40]と同様な導出により,次の通り 0.67
(cid:104)Ovl(cid:105 ) = εvt−1,vl · sin(βπ) sin(εvt−1,vl γ) (cid:104)Ovl(cid:105 ) = εvt−1,vl · sin(βπ) sin(εvt−1,vl γ) 0.40
· (cid:89) (vl,k)∈E k(cid:54)=vt−1 ·(第89回) (vl,k)・Ek(cid:54)=vt−1 0.54
cos(εvl,kγ), cos(εvl,kγ) 0.46
(B1) where vt−1 is the last node in the partial tour and vl is the candidate node. (B1) vt−1 は部分巡回の最後のノードであり、vl は候補ノードである。 0.63
By the identity cos(θ) = sin( π 恒等式 cos(θ) = sin( π) により 0.87
2 − θ) we can rewrite eq. 2 − θ) eq を書き直すことができる。 0.85
(17) as (cid:16) π (cid:104)Ovl(cid:105 ) = εvt−1,vl · sin(βπ) sin(εvt−1,vl γ) 17) (cid:16) π (cid:104)ovl(cid:105 ) = εvt−1,vl · sin(βπ) sin(εvt−1,vl γ) 0.43
(cid:17) − εvl,kγ (cid:17) −εvl,kγ 0.40
. (B2) · (cid:89) . (B2) ·(第89回) 0.53
(vl,k)∈E k(cid:54)=vt−1 (vl,k)・Ek(cid:54)=vt−1 0.38
sin 2 Let us now assume that we want to construct a fixed (but arbitrary) tour T . 罪 2 さて、修正された(しかし任意の)ツアーtを構築したいと仮定しましょう。 0.47
First, we notice that the term sin(βπ) does not depend on vt−1 or vl and is the same for all vl. まず、 sin(βπ) という用語は vt−1 や vl に依存しず、すべての vl に対して同じであることに気づく。 0.78
This means that this term can merely flip the sign of all (cid:104)Ovl(cid:105 ), and from now on w.l.o.g. we assume that β is such that the term is positive. これは、この項が単にすべての (cid:104)ovl(cid:105 ) の符号を反転させることができることを意味する。
訳抜け防止モード: これは、この用語が単にすべての(cid:104)Ovl(cid:105 )の符号を反転できることを意味する。 今後、w.l.o.g.では、β は正の項であると仮定する。
Now we can again formulate the tour generation task in terms of a binary classification problem, where we want to find a configuration of labels for our remaining sin terms in eq. 現在、我々は再びツアー生成タスクを二項分類問題の観点から定式化することができる。
訳抜け防止モード: 現在、二項分類問題の観点からツアー生成タスクを定式化することができる。 eqの残りの罪条件のラベルの 構成を見つけたいのです
(B2) s.t. the product will have the highest expectation value in each node selection step for the edge that produces the ordering we have chosen for T . (B2) 積は、T に対して選択した順序を生成するエッジに対する各ノード選択ステップにおいて、最も高い期待値を持つ。 0.85
Again, we can accomplish this for arbitrary settings of edge weights by only considering the sign of the resulting product. 繰り返しますが、結果の製品のサインだけを考慮すれば、エッジウェイトの任意の設定でこれを達成できます。 0.59
This means that we have to find an assignment of the edges εij to the classes f± that at each step of the node selection process will lead to the node being picked that we specify in T . これは、ノード選択プロセスの各ステップで、tで指定したノードが選択されるような、クラスf±へのエッジεijの割り当てを見つける必要があることを意味する。 0.69
As all edges can occur in the above products multiple times during the node selection process, this is a non-trivial task. すべてのエッジが上記の製品でノード選択プロセス中に複数回発生するため、これは非自明なタスクである。 0.76
However, if we can guarantee that each (cid:104)Ovl(cid:105 )t at node selection step t contains at least one unique term that is only present in this specific expectation value, we can use this term to control the しかし、ノード選択ステップtにおける各(cid:104)ovl(cid:105 )tが、この特定の期待値にのみ存在する少なくとも1つの一意的な項を含むことを保証できれば、この用語を使って制御することができる。 0.72
sign of this specific value. この特定の値のサイン。 0.70
Each εij occurs either in the leading term sin(εijγ) (corresponding to the candidate edge to be potentially added in the next step) 2 − εijγ) (correspondor in the product term as sin( π ing to an outgoing edge from the current candidate). 各εij は、先頭の項 sin(εijγ) (次のステップで潜在的に追加される候補辺に対応する) 2 − εijγ (現候補から出る端への積項 sin(π ing) で対応する) で現れる。 0.77
We can easily see that the leading term only appears in the case when we ask for this specific εij to be the next edge in the tour, and from definition 2 we know that this only happens once in the node selection process. この特定のεijがツアーの次のエッジであるように要求された場合にのみ、先頭の用語が現れることが容易に分かり、定義2から、これはノード選択プロセスで一度だけ発生することが分かる。 0.71
In all other expectations, εij appears only with the “offset” of π 2 . その他の予想では、εij は π 2 の "オフセット" にのみ現れる。 0.70
This means that this leading term is the unique term that we are looking for, as long as sin(εijγ) (cid:54)= sin( π 2 − εijγ), so as long as sin(εijγ) (cid:54)= cos(εijγ). これは、この先行項が我々が探している唯一の用語であることを意味する: sin(εijγ) (cid:54)= sin(π2 − εijγ) であり、 sin(εijγ) (cid:54)= cos(εijγ) である。 0.79
We know that cos(θ) = sin(θ) for θ = π θ = π に対して cos(θ) = sin(θ) であることが分かる。 0.85
4 + nπ with n ∈ Z. So as long as + nπ ∀ n ∈ Z, εij ∈ E, 4 + nπ で n ∈ z である限り、 + nπ で n ∈ z, εij ∈ e である。 0.91
εijγ (cid:54)= εijγ (cid:54)= 0.35
π 4 (B3) and all εij are unique, our ansatz can construct the π 4 (B3) 全てのεij はユニークで、我々のアンサッツは 0.62
desired tour T . In this case, we have a guarantee that we can construct the tour T for any configuration of edges that fulfills eq. 所望のツアーt。 この場合、eqを満たすエッジの任意の構成に対して、ツアーTを構築することができるという保証がある。 0.69
(B3). In particular, this means that we can construct the optimal tour in this way. (B3)。 特にこれは、この方法で最適なツアーを構築することができることを意味する。 0.54
19 Additionally, due to equivariance of our model under node permutations, it is sufficient to find just one of these settings for any tour T and use this to construct the optimal tour. 19 さらに、ノード置換の下でのモデルの同値性により、任意のツアーTに対して、これらの設定のうちの1つだけを見つけ、これを最適ツアーを構築するために使うのに十分である。 0.48
We can do this because once we have found a labeling of the edges for the classes f± that produces a given tour sequence, we can simply reshuffle our nodes s.t. this sequence of the “physical nodes” (indices corresponding to qubits) will produce the optimal tour for our “logical nodes” ((x, y) coordinates of graph nodes). 与えられたツアーシーケンスを生成するクラスf±のエッジのラベルが見つかったら、単にノードs.tを書き換えることができます。 この“物理ノード”(キュービットに対応するインデックス)のシーケンスは、私たちの“論理ノード”(グラフノードの(x, y)座標)の最適なツアーを生成します。 0.73
However, note that this can not be used to trivially find the optimal tour, as it amounts to trying all (n−1)! しかし、これは全ての (n−1) を試すことになるので、最適ツアーを自明に見つけるには使用できないことに注意してください。
訳抜け防止モード: ただし、これは使用できない点に注意。 最適なツアーを見つけるのに役立ちます すべての (n−1 ) を試すのと同じです!
possible tours. 2 ツアーも可能。 2 0.57

翻訳にはFugu-Machine Translatorを利用しています。