WIDE

Sprouting Research -研究の芽-

WIDEプロジェクトはさまざまな産学組織の研究者・技術者・運用者から成り立っています。組織の枠を超えたつながりの中で、インターネットをはじめとする広域分散処理技術を中心に、より便利で安全な未来を目指した技術開発と研究が進められています。ここでは、その中から若手研究者が取り組んでいる研究課題を取り上げ、これから世に出ていく新しい技術と、その研究開発に取り組む姿を紹介します。

01 より自由な経路制御を目指して

より高度で柔軟なトラフィックエンジニアリングやサービスファンクションチェイニングなどへの応用に向けて、新しい経路制御技術であるセグメントルーティングが注目を集めています。今回はその次世代経路制御技術に興味を持ち、セグメントルーティングが抱える規模性の解決に取り組む研究者を紹介します。

三島航

北陸先端科学技術大学院大学
篠田研究室 修士課程 三島 航(みしま わたる)

北陸先端科学技術大学院大学 篠田研究室 修士2年の三島航です。セグメントルーティングにおける階層化について研究を行なっています。WIDEプロジェクトには2017年の7月から参加しています。 WIDEでの主な活動としては、2018年春の研究会でインフラワークショップ開催、秋合宿で会場ネットワーク構築・ポスター発表を行いました。その他の活動としては、2018年のInterop ShowNetにSTMとして参加しました。普段の生活でも研究室ネットワークの管理・運用を行なっています。

セグメントルーティングとは

セグメントルーティング(以下、SR)とは、経路の各要素をセグメントと呼ばれる単位で表現し、経由先や宛先として指定することで柔軟な制御を実現する技術です。SRはシンプルかつ柔軟な経路制御技術として、トラフィックエンジニアリングやサービスチェイニングなどでの利用が期待されています。以下にSRの概念図を載せます。

SR概念図

SRではセグメントを表すため、セグメントID(SID)と呼ばれる識別子を用います。送信元ノードで、セグメントリストと呼ばれる経由セグメントのSIDリストをパケットに付加することで経路を指定し、転送を行うソースルーティングの一種です。

セグメントにはノードを示すNodeセグメントと、隣接関係を示すAdjacencyセグメントの二種類が存在します。Node SIDが指定された場合はそのノードへのアンダーレイネットワークにおける最短経路を用い転送が行われます。Adjacency SIDが指定された場合、Adjacency SIDが示すインターフェースから送出が行われます。

上の図にSRにより転送を行う様子を示しました。この例は、8番から5番のノードへと送信するパケットを、最短経路ではなく4、1のノードを経由するように経路制御した例となります。そのため転送対象のパケットに「8-4、1、5」というセグメントリストを付加しています。

SRに参加するノードの集合をSRドメインと呼びます。各ノードはSRドメインに参加する全ノードのNode SIDと、自らのインターフェースのAdjacency SIDを格納したSIDテーブルを保持しています。各ノードは受け取ったパケットのセグメントリストの先頭要素を確認し、SIDテーブルを参照することで次の宛先を決定し、送出を行います。

スケーラブルな運用を目指して

SRの問題点として、各ノードがSRドメインの全ノード分のNode SIDをSIDテーブルに持たなければならない点があります。これにより、参加ノードが増加すると各ノードが持つべきSIDテーブルの情報量が増加し、メモリ量と検索時間の負荷による規模性の問題が生じます。この対策として、私の研究ではSRの階層化を提案しています。提案手法である階層的SRの概念図を以下に示します。

階層化の概念図

左側が既存のSR、右側が階層的SRを示しています。階層的SRではSRドメインをサブドメインに分割し、各ノードに自らの属するサブドメイン内の情報のみを持たせることで情報量を削減し、規模性を確保します。図の例では、23番のノードはサブドメインC内部の21、22、24の情報のみに抑制できます。

情報量を削減した上で正しく転送を行うため、本研究では二種類の手法を提案しました。 以下にそれぞれの概念図を示します。

階層的SRのモデル分類

1つ目は上位SIDモデルです。このモデルでは各サブドメインにSIDを付与し、経由先として指定することでサブドメインを超えた転送を可能にします。図の例では、サブドメインにそれぞれ0、10、20というSIDを付与しています。このモデルはで上位SIDを指定可能なため、次に扱う展開モデルに比べセグメントリストを短く構成することが可能になりますが、サブドメインに付与したSIDを扱えるようデータプレーンの拡張が必要となります。

2つ目は展開モデルです。このモデルでは各ノードがサブドメイン内の情報のみで転送を行えるよう、セグメントリストを構築します。図の例では、23のノードはサブドメイン内の22へ、22のノードはAdjacency SIDを用い隣のサブドメインへ、というようにサブドメイン内の情報のみで転送する様子を示しています。このモデルでは既存のSRと同じSIDを利用するため、データプレーンの拡張は不要です。しかしサブドメイン間を移動する際必ずAdjacency SIDを指定する必要があるため、上位SIDモデルに比べセグメントリストは増大します。本研究では、まず実装負荷の低い展開モデルから実装を行なっています。

研究の魅力と手を動かす面白さ

この研究の面白い要素として、サブドメインサイズとパフォーマンスの兼ね合いや、アンダーレイプロトコルの規模性との兼ね合いなど、実際に動かしてみないとわからない要素が多い点があります。また、SRは新しいトピックであり、手を動かすことで切り開いていくというやりがいも大きいです。

現在、OSSのルーティングデーモンであるFRRoutingとLinux KernelのMPLSで実装を開始しています。今後は修了までに階層的SRの実装と評価を進めていきます。またその中で、MPLS-TEやSRv6なども扱って行きたいと考えています。進捗や調査項目などは研究ページ(https://watal.github.io/)に随時更新していきます。 FRRoutingを用いた実験方法を記事にまとめているので、ぜひ試してみてください。

(2018年12月)

次回は北陸先端科学技術大学院大学の宮崎駿さんの研究を紹介します。

02 コネクテッドカーを守る

自動車の情報化はめざましい勢いで進んでいます。今後はより強固にインターネットと接続し、高度なサービスを提供するようになるでしょう。パソコンなどと違い、自動車では小さな不具合が人命に関わる事故につながることがあります。安全なネット接続は必須条件です。今回は、自動車の高度化を推進しながら、安全なネットサービスの実現を目指す研究者を紹介します。

宮崎駿

北陸先端科学技術大学院大学
篠田研究室 修士課程 宮崎 駿(みやざき しゅん)

北陸先端科学技術大学院大学 篠田研究室 修士2年の宮崎駿です。自動車のハニーポットについて研究を行なっています。WIDEプロジェクトには2017年の7月に参加しました。以後、2018年春の研究会運営、研究会での研究成果報告、2018年の秋合宿研究会での会場ネットワーク構築、ポスター発表、またBSD BoFの開催などに取り組んできました。

研究の始まり

私は文系学部出身であり、学部時代に自動車の研究をしていた訳ではありませんでした。この研究テーマを思いついたのは修士1年の時です。研究室ゼミで指導教官から、「コンピュータを繋いだら自動車のあらゆるデバイスを不正に操作できる」と教えられ、衝撃を受けたことからこの研究に興味を持ちました。調査を進める中で、実際の自動車を遠隔から操作できることも知りました。その後、車載ネットワークシミュレータについて調査した際に、車載ネットワークがインターネット側から見えるような仕組みを作れば、遠隔攻撃を試みる攻撃者を誘い込むハニーポットになると気がつき、研究に取り掛かりました。

自動車のハニーポット

近年、コネクテッドカーなど無線接続によって外部と通信する機能を持つ自動車が増加しており、今後もこの傾向は続くと予想されます。これによって車載ネットワークに対する遠隔からのサイバー攻撃が懸念されます。遠隔から車載ネットワーク内部に不正なメッセージを送信することで、ステアリングやブレーキなどに対する不正な操作が可能であることはすでに実験で実証されています。自動車への攻撃は車内・車外の人々の安全を脅かすものであるため、車載ネットワークへの遠隔攻撃に備えたセキュリティ対策が必要不可欠です。

研究では、セキュリティ対策のためのひとつのアプローチとして自動車のハニーポットを提案しています。自動車のハニーポットとは、インターネットから車載ネットワークに模した環境へのアクセスを提供し、攻撃者に対しては、あたかもその先に本当の車載ネットワークがあるかのように見せつつ、車載サービスを提供する仮想環境と監視機構を用意したものです。

ハニーポットの作成にあたり、インターネットに接続する可能性のある自動車のアタックサーフェスを整理しました。以下にその概念図を示します。

インターネットに接続する可能性のある自動車のアタックサーフェス

インターネットに接続する可能性のある車載デバイス(エッジデバイス)として、インフォテイメントシステムとOBD-IIドングルが挙げられます。インフォテイメントシステムはスマートフォンのテザリングや3G・4Gのような通信機能を経由してインターネットに接続している可能性があります。一方、OBD-IIドングルの場合は、ELM327のようなドングルを用いてインターネットに接続している可能性があります。

OBD-IIとは自動車の診断を行うことを目的としたコネクタのことです。このコネクタになんらかのドングルを接続することで車載ネットワーク内のデータを読み書きすることができます。Wi-Fiインタフェースを備えたELM327の場合、ELM327自身がWi-Fiアクセスポイントとなります。そこにWi-Fi経由で端末を接続し、ELM327の持つIPアドレスと特定のポート番号にtelnetで接続、任意のコードを入力することで車載ネットワーク内のデータを操作できます。

ここで重要なことは、インターネット側から車載ネットワークにアクセスするには必ずゲートウェイと車載デバイスに相当する2つの機器を経由する必要があるということです。

自動車のアタックサーフェスを参考にハニーポットの構成モデルを考えたものが以下の表になります。

ハニーポットの構成モデル

ハニーポットの構成要素はゲートウェイ・車載デバイス・車載ネットワークの3つです。車載デバイスの種類によって、インフォテイメントシステム型とドングル型の2つの構成モデルがあります。インフォテイメントシステム型ではインフォテイメントサービスの基盤としてQNXやAGL(Automotive Grade Linux)などのOSが動作しています。ドングル型では車内ネットワークに流れるデータの受け渡しが可能なドングルが利用されていることを想定しています。

構成モデルを踏まえてハニーポットの実装戦略を考えたものを以下の図に示します。

車のハニーポットの実装戦略

研究では、構成パターンとして実装負荷の少ないドングル型を採用しました。ドングルはELM327を想定しています。車載ネットワークを再現するため、ハニーポットの稼動前に実車両から車載ネットワークに流れるデータをレコーダで記録し、データベースに保存しておきます。ハニーポット稼働時はこの記録したデータを再生機でELM327シミュレータに渡します。この再生機が実車両内に流れるデータを再現します。攻撃者はインターネット側からゲートウェイ機器に接続し、その先にあるELM327シミュレータに接続される仕組みになっています。ELM327シミュレータのインタフェースには再生機の他に、実車両や車載ネットワークシミュレータからデータを渡すことも可能です。

研究の醍醐味

今後、コネクテッドカーやIoT(Internet of Things)などのV2X(Vehicle to everything)技術が発展していく中で、自動車のセキュリティは重要性を増し続けます。現在、自動車への攻撃を捉え、分析するための実装は世の中にはまだありません。そのため誰も見たことのない領域で作業し、研究できる面白さ、楽しさを感じています。また、ハニーポットを作成するにあたっては、攻撃者の車載ネットワークに対する遠隔攻撃プロセスを予測することが必要です。予測した上でより攻撃を誘引しやすいハニーポットの環境はどうあるべきかを考えることは、攻撃者との化かしあいのようなもので面白いです。

今後の計画

現在の実装戦略では攻撃者に対するゲートウェイの見せ方を検討しきれていません。そのため、ゲートウェイがどういった環境であれば攻撃者を誘引できるか、その条件を検討する必要があります。今後、実装戦略で示したドングル型のハニーポットを実装を完成させ、稼働実験、評価していく予定です。

(2019年1月)

次回は名古屋大学の浦野さんの研究を紹介します。

03 地下街で迷わない技術

スマートフォンを用いた位置情報の活用は、今や日常生活に欠かせない技術となりました。いつでもどこでも地図と現在位置を確認できるようになり、迷子で遅刻することも少なくなったのではないでしょうか。現在、位置情報はGPS衛星からの電波を観測することで提供されていますが、GPSの電波は地下には届きません。今回は、電波の届かない場所でも正確な位置情報を提供する仕組みに取り組む研究者を紹介します。

浦野健太

名古屋大学大学院
河口研究室 博士課程 浦野 健太(うらの けんた)

名古屋大学大学院 河口研究室D1の浦野です。Bluetooth Low Energy (BLE)を用いた位置推定技術について研究をしています。WIDEプロジェクトには2015年の3月から参加しています。
WIDEでは、2015年春合宿でのUnconferenceにおける発表、春研究会での研究発表、夏合宿でのPCなどを行いました。研究室では日々の研究に加えて、生徒共用のサーバを一部管理しています。

名古屋大学・河口研究室では行動センシング、交通データ解析、コンピュータビジョンなど様々な研究が行われています。どの研究も実世界データを利用しており、人がより快適に生活できる技術の開発を目指しています。今回は、私が取り組むBLEによる位置推定について紹介します。

屋内位置推定技術

スマートフォンが普及し、誰でも簡単に自分の位置情報を取得できるようになりました。例えば、地図アプリによる経路案内や、今どこにいるのかのSNS投稿などが挙げられます。実世界の位置を利用するゲームも近年人気を集めています。

これらで利用される位置情報は、主にGPSを利用して取得されています、GPS衛星との通信で地上における自身の位置を特定するのですが、通信状況によっては取得される位置に大きな誤差が生じます。屋外でもビルの多い場所や屋根の下では誤差が大きくなりますが、建物の中・地下街などの屋内では常に誤差が大きいか、そもそも位置が取得できません。そこで、GPSに頼らず位置を推定する方法(=屋内位置推定技術)が研究されています。

屋内位置推定技術により、地下街やショッピングモールにおいて、特定の店までのナビゲーションや、工場内を動くロボットの監視が可能になります。また、人が店内のどの棚の前にいるか、展示会でどのブースの前にいるかなど、興味に関わる情報を取得し、行動分析やマーケティングに利用することも考えられます。

屋内位置推定手法は、推定対象や利用する環境に応じて、加速度や角速度のセンサ信号を使うもの、超音波やレーザを使うもの、RFIDやWi-Fi電波強度を使うものなど多数提案されています。私はそれらの中でもBluetooth Low Energy (BLE)タグを利用したイベント向け位置推定について研究を行っています。

BLEを利用した位置推定

BLEは名前の通りBluetoothの規格の一部で、低消費電力に主眼をおいており、スマートフォンとスマートウォッチの接続や、PCとワイヤレスマウスの接続などに利用されています。また、特定の情報を含むパケットを一定間隔で発信しつづけるBLEビーコンを利用したサービスもあります。

本研究で提案するBLEを利用した位置推定では、BLEビーコンと、BLEビーコンからの電波を受信するスキャナを利用します。位置推定のイメージを下の図に示します。BLEビーコンは人が持ち、スキャナは対象エリアに複数台を分散して設置しておきます。各スキャナは人までの距離に応じて異なる電波強度を観測します。現在はこれらの電波強度から三点測位を行い対象者の位置を推定しています。

位置推定

しかし、BLEの電波は不安定で、ノイズや障害物の存在で強度が簡単に変動してしまいます。そこで、本研究では前回の推定位置をもとに、次の推定位置候補となる多数の点(パーティクル)を散布し、尤もらしい位置を探すパーティクルフィルタで安定した推定を目指しています。

パーティクルフィルタ

実際に日本科学未来館で行われたイベントにおける位置推定では、反時計回りに会場内を一周する経路で次の図のような結果になりました。図では、青から緑に変わる点が実際の歩行経路を、ピンクから黄色に変わる点が推定した歩行経路を示しています。

推定サンプル

パケットロスの低減への取り組み

前節でも述べたとおり、BLEの電波は不安定です。強度の変動はもちろん、そもそも電波を受信できない(パケットロス)こともしばしばあります。そこで、ハードウェアの改良として、1つのスキャナに複数のBluetoothアダプタを取り付けたタンデムBLEスキャナを利用し、パケットロスの低減に取り組んでいます(実物は下の図のようになっています)。副次的な効果として、同じパケットを複数のBluetoothアダプタで観測することがあるため、位置推定で利用する電波強度をよりロバストに取得することもでき、精度の向上に繋がりました。

タンデムBLEスキャナ

幅広い知識に触れつつ試行錯誤する面白さ

本研究では、アルゴリズム的な部分だけではなく、ハードウェア面でも工夫を施して精度の改善をはかっています。その過程で3Dモデリング/3Dプリンティングや、Raspberry Piなどにも触れており、様々な知識を得られています。電波という目に見えないものを相手にしているので難しい部分も多いですが、工夫の幅も広く、あれこれ試す面白さがあります。

現在はシミュレーションで仮想的に生成した電波強度データで学習したニューラルネットワークを用いて、実際に観測した電波強度データに対する位置推定に取り組んでいます。BLEの電波強度は環境への依存度が大きく、人が移動しなければならないため、大量のデータ収集は困難です。シミュレーションを用いてデータ収集の労力を大きく減らせれば、高精度な位置推定を利用しやすくなると考えられます。

(2019年2月)

04 機械学習を活用したリアルタイム悪性通信遮断

悪質なトラフィックを遮断する技術としてパターンマッチなどによるフィルタ技術が広く利用されていますが、より柔軟な対応を実現するため機械学習などの応用が盛んに進められています。ここでは、機械学習など処理負荷の高い技術を、高速ネットワークに応用するための技術に取り組んでいる研究者を紹介します。

須賀灯希

東京大学大学院情報理工学系研究科電子情報学専攻
江崎落合研究室 修士課程 須賀 灯希(すが ゆうき)

東京大学大学院 情報理工学系研究科 電子情報学専攻 江崎落合研究室修士2年の須賀灯希です。WIDEプロジェクトには学部4年の時から参加しています。これまで2017年春の研究会でポスター発表を行い、2017年と2018年の秋合宿ではPCとして参加しました。

サイバーセキュリティとの関わり

サイバーセキュリティ分野に興味があり、卒論ではDTLSサーバへのDoS攻撃の対策をテーマとしていました。修士では違うテーマにも取り組みたいと思い、またWIDEの縁でNetwork Muscle Learning (NML) project (Web: https://www.nml.ai) に参加させていただくことになり、現在のテーマになりました。

機械学習の利点と欠点

私の研究テーマは機械学習による悪性トラフィック遮断のための高速パケット分類システムの実現です。巧妙化するサイバー攻撃の検知精度を高めるために、既存のブラックリスト等のパターンマッチングだけでなく、機械学習を用いた攻撃検知手法が近年盛んに研究されています。しかし一般的には機械学習による分類処理はパターンマッチングよりも大きな処理時間を要し、既存研究のほとんどが検知に要する処理時間を考慮していません。また攻撃によるインシデントを未然に防ぐには、ネットワーク上に置かれたファイアウォールのように悪意あるパケットを攻撃対象端末に到着する前に遮断することが肝要です。しかし、通信の良性・悪性判断に時間を要してしまうとネットワークの遅延につながります。こうした背景を踏まえ、本研究ではネットワークの遅延を最小限に抑えつつ機械学習を利用したパケット分類システムの実現を目的としています。

柔軟性と即応性を兼ねたトラフィック分類

まず予備実験として、図1のような、学習済みモデルを用いた悪性パケット分類システムを構築し性能評価を行いました。本システムはネットワーク上に設置され、受信したパケットから必要な情報を抽出し、それを特徴量ベクトルに変換し学習済み分類器に入力します。そして分類結果に応じて当該パケットを送信または破棄します。システムの実装には、パケット送受信にData Plane Development Kit (DPDK)ライブラリ、分類モジュールとしてRandom Forest (OpenCV)、Support Vector Machine (LIBSVM)、Neural Network (Tensorflow) の3種類の機械学習ライブラリを使用しました。実験では多数のDNSクエリからマルウェアが自動生成 (DGA) した悪性クエリを分類するタスクを設定し、パケット転送時間を計測しました。結果は分類モジュールを組み込まない場合と比較して転送時間が約100倍に増加し、転送時間をスループットに換算すると最大でも10Mbpsとなりました。

学習済みモデルを用いた悪性パケット分類システム
図1 学習済みモデルを用いた悪性パケット分類システム

計測結果を踏まえ、パケット転送遅延をさらに抑えるために、分類対象プロトコルをDNSに絞りDNSの名前解決の仕組みを活用することにしました。DNSの名前解決において、キャッシュサーバがクライアントからクエリを受信し名前解決を行い、結果をクライアントに送信するまでには時間を要します。本研究では名前解決を実施している間に分類処理を実行することを考えました。分類システムをクライアントとキャッシュサーバの間に設置し、クライアントから受信したクエリをキャッシュサーバに転送後、分類処理を名前解決の間に実行し、分類結果に応じてキャッシュサーバからの応答を遮断することで、パケット転送遅延を抑えつつ悪性ドメイン名の名前解決を防止できます。図2に提案システムの概要を示します。システムはクエリを受信後すぐにキャッシュサーバに転送します。その後キャッシュサーバによるクエリの名前解決が行われている間に分類処理を行い、分類結果をブラックリスト・ホワイトリストに反映させます。クエリに対する応答が返ると応答をブラックリスト・ホワイトリストと照合させ、ブラックリストと一致した場合は応答を破棄します。転送処理においてパケットはパーサとフィルタリングモジュールのみを通過するため、機械学習による分類処理を挟んだ場合よりも転送時間を削減できます。予備実験と同様の実験により提案システムを評価した結果、実験環境では名前解決に1 - 10msを要し、この時間内に処理が終わる分類モジュールを用いれば悪性DNSクエリに対する応答を遮断できることを確認しました。また、DNSクエリの転送時間は予備実験で用いたシステムよりも削減されることを確認しました。

DNSの名前解決時間を活用した提案システム
図2 DNSの名前解決時間を活用した提案システム

今後の抱負

検知対象の拡大・複数の分類モジュールの並列化など、研究目標の実現のためにはまだまだ解決すべき課題がたくさんありますが、修了までに1つでも多く解決できるように頑張ります。

(2019年3月)

05 Applying Measurement-based Quantum Computing to Quantum Network Coding

量子情報の転送を用いた量子通信は次世代の安全な通信技術として注目されており、将来の実用化に向け、多くの研究者が課題の解決に取り組んでいます。今回は、より効率的な量子ネットワークの実現を目指して研究を進める若手研究者を紹介します。

松尾賢明

慶應義塾大学大学院
村井研究室 修士課程 松尾 賢明(まつお たかあき)

慶應義塾大学大学院 村井研究室 修士2年の松尾賢明です。2016年の2月にWIDEプロジェクトに参加し、現在は主にワーキンググループ AQUAにて量子通信に関連した研究を幅広く行なっています。WIDE2018年秋合宿研究会ではエンドツーエンド量子通信の確立に関する研究のポスター発表や、量子計算/通信をテーマとしたBoFを主催しました。

Network coding

Network coding is a communication technology used for alleviating bottlenecks in a network to improve the aggregate throughput. The most basic topology that is solvable by network coding is known as the butterfly network. The classical form was discovered by Ahlswede, Cai, Li, and Yeung [1].


Network coding over a butterfly network

In the above example, source nodes \(S_{1}\) and \(S_{2}\) each own a 1-bit of data, \(X\) and \(Y\), with the goal of delivering them to target nodes \(T_{1}\) and \(T_{2}\) respectively. Assuming that each link has a capacity of 1 bit per unit time, the link between intermediate nodes \(r_{1}\) and \(r_{2}\) becomes a bottleneck - both X and Y cannot be delivered to \(r_{2}\) from \(r_{1}\) at the same time.

For such cases, network coding allows us to transmit both messages simultaneously. As in the figure above, each source node forwards the message to both adjacent nodes. The intermediate node \(r_{1}\) linearly combines the messages, X and Y, using an XOR operation, and forwards the encoded message to both target nodes \(T_{1}\) and \(T_{2}\) via \(r_{2}\). In the end, the target nodes can reconstruct the original message by decoding the encoded message.

Similar bottleneck problems also occur in quantum communication. There are several quantum network coding protocols published (including work by WIDE member Takahiko Satoh), however, the main problem was that they were mainly based on the classical algorithm, which resulted in deeper circuit depth causing errors in the computation, known as infidelity. One of my research themes was to design a simpler quantum network coding scheme based on measurement-based quantum computing for quantum repeater networks. The published full paper about the work can be access here [2].

Quantum repeater networks

The quantum repeater is considered to be an essential component for achieving a robust quantum communication system. A quantum repeater node consumes a special type of quantum resource called entanglement to deliver arbitrary data qubits across a network.

Like a classical bit, a qubit is the smallest unit of quantum information. A single qubit can be in more than one states simultaneously, which is known as the superposition state.

$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}\\ \ket{\psi} = \alpha \ket{0} + \beta \ket{1}\\ s.t. \mid \alpha \mid^2 + \mid \beta \mid^2 = 1 $$ The \(\ket{}\) is Dirac's ket notation for a vector. Coefficients \(\alpha\) and \(\beta\) are arbitrary complex numbers representing the probability amplitudes. The actual probability of the state can be found by taking the absolute value square of the coefficient of the term of interest.

Entangled qubits have characteristics that cannot be replicated by any classical systems. The state of a qubit that is entangled with another cannot be described independently, regardless of how far apart they are located. One of the simplest entangled states involving two qubits, is known as the Bell state, where one of the bases can be described as :

$$ \ket{\Phi^+} = \frac{1}{\sqrt{2}}(\ket{0_{A}0_{B}} + \ket{1_{A}1_{B}})\\ $$

Here, two qubits, A and B, are entangled so that their state is in a superposition state of both being \(\ket{0_{A}0_{B}}\) and \(\ket{1_{A}1_{B}}\) with equal probability (\((\frac{1}{\sqrt{2}})^2 = \frac{1}{2} = 50\%\)). Thus, measuring either of the two qubits destroys the superposition state. In the real world, qubits and its carrying information may be, for example, implemented by using single photons and their polarizations.

The process of delivering an arbitrary quantum information from one place to another by consuming an entangled resource is called quantum teleportation.


Procedure of quantum teleportation. Quantum teleportation requires classical communication for sharing the measurement results. The last gate operation depends on the received measurement results.

The CNOT gate is the quantum equivalent of the classical XOR gate. Therefore, similar to the XOR gate, we need two qubits - the control qubit and the target qubit. The CNOT gate flips the target qubit's state from \(\ket{0}\) to \(\ket{1}\) and from \(\ket{1}\) to \(\ket{0}\) if and only if the control qubit's state is \(\ket{1}\). The Hadamard gate (H gate) brings up a single qubit into a superposition state from a basis state, or vice versa. An example of its usage may be, \(H\ket{0} = \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) = \ket{+}\) and \(H\ket{1} = \frac{1}{\sqrt{2}}(\ket{0} - \ket{1}) = \ket{-}\). The X gate is similar to the classical NOT gate, and flips the bit information of a single qubit. Thus, \(X \ket{0} = \ket{1}\) and \(X \ket{1} = \ket{0}\). The Z gate, simlar to the X gate, flips the phase information of a qubit, hence resulting in \(Z\ket{+} = \ket{-}\) and \(Z\ket{-} = \ket{+}\). Because a single qubit has two degree freedoms (the bit information and the phase information), there are more than one type of single qubit measurements (X,Y and Z measurements). Though they act similarly to the classical read operation, only a part of the state's knowledge can be extracted.

For multi-hop quantum communication, the simplest strategy is to teleport the data qubit hop-by-hop. Nevertheless, this method is known to be impractical in terms of error management. Instead, we teleport one of the qubits that is entangled with another to physically lengthen the distance of the entangled resource. This technique is called entanglement swapping.


Procedure of entanglement swapping. Bell pairs along the path gets connected via entanglement swapping to directly connect the source to destination.

Without quantum network coding, the bottleneck problem over a butterfly network may be solved by multiplexing schemes, such as the time-divition multiplexing.

Measurement-based quantum network coding

The goal of quantum network coding for repeater networks is to generate two crossing over resources simultaneously.


Goal of quantum network coding.

My work focused on simplifying the procedure between the input state and the output state by taking full advantage of the unique characteristics of measurement-based quantum computing (MBQC).

MBQC is an alternative universal computation scheme based on single qubit measurements over square lattice cluster states, which is commonly a system area network. Any single qubit unitary operation (e.g. X gate) can be, for example, substituted by a sequence of three measurements over a chain of four qubits.

A cluster state can be generated by preparing all qubits as \(\ket{+}\) state first, and by performing Controlled-Z gates between any qubits to make an a new edge/entanglement.

Thus, a cluster state with \(n\) qubits can be defined by :

$$ \ket{G} = \prod_{(a,b) \in E} CZ_{a,b}\ket{+}^{\otimes n} $$

where E is the set of edges/entanglement and a, b are the corresponding vertices/qubits in the cluster state. A cluster state with only two qubits, qubit A and qubit B, is \(\ket{G}=\frac{1}{2}(\ket{0_{A}0_{B}}+\ket{0_{A}1_{B}}+\ket{1_{A}0_{B}}-\ket{1_{A}1_{B}})\), which is almost equivalent to a Bell pair because \(H \ket{\Phi^+} = \ket{G}\) with the Hadamard gate applied to either qubit.


A pictorial example of a square lattice cluster state generation. In MBQC, Qubits are measured along different axis depending on the operation, from left to right concurrently.

Being able to compute solely based on measurements is indeed an interesting fact. Another characteristics, which I took advantage of in my research, is the topological transition of the cluster state caused by qubit measurements.


Topological transition of a cluster state invoked by a single qubit measurement. The X measurement requires an extra gate operation to one of its neighbors.

In my research, I assumed repeater nodes with the ability to distribute two qubit cluster states between adjacent nodes, and proposed/analyzed a measurement based operations on resources to directly connect both source nodes to target nodes simultaneously. Three simple steps can transform the initial state to the desired output state.


Encoding procedure of measurement-based quantum network coding.

My proposed method has successfully reduced the circuit depth by 56.5% from a previously known quantum network coding protocol [3].

What makes the research exciting

I joined AQUA because I took Higher Level mathematics, physics and computer science for the IB program in back high school, and wanted to use everything I learned at the same time.

It is simply very interesting and challenging for me to come up with ideas and solutions that completely differ from the classical systems. Quantum computing/communication is still under development, but they are growing very rapidly nowadays. Today, we have access to one of the best quantum computers in the world, developed by IBM, and have tremendous opportunities to work on the real world problems. It is one of the most exciting times I have, to be able to actually contribute to the very deepest core of the next generation technology.

Future work

Currently, I am working on building a quantum Internet simulator. In the future, I expect the simulator to be able to analyze various protocols, including quantum network coding, to gain new knowledge with more details.

To learn more

If you are interested in quantum networking, please contact to AQUA(aqua@sfc.wide.ad.jp) or to me (kaaki@sfc.wide.ad.jp) directly.

[1] R. Ahlswede, N. Cai, S. Y. Li, and R. W. Yeung, IEEE Trans. Inf. Theor. 46, 1204 (2006).

[2] T. Matsuo, T. Satoh, S. Nagayama and R. Van Meter, Phys. Rev. A 97, 062328 (2018).

[3] T. Satoh, F. Le Gall, and H. Imai, Phys. Rev. A 86, 032331 (2012).

(2019年4月)