Jij Tech Blog

Jij inc.の開発日記です

OpenJijを使ったスピングラスの数値計算

この記事は2021年物理学アドベントカレンダーの3日目です。 2021年のアドベントカレンダーということなので2021年のノーベル物理学賞の一つのスピングラスを題材にしたいと思います。 さっそく本題のOpenJijを使った数値計算について知りたい方はここに飛ん…

熱浴法、模擬焼き鈍し法と種々のアルゴリズム、及びそれらの収束定理

熱浴法で更新する場合の、イジング模型と呼ばれる\{-1,+1\}^Nを定義域とする多項式函数の最小に近い解を求めるための、有名な古典アルゴリズムである模擬焼き鈍し法の説明およびその収束定理(Geman-Geman)を、原論文を和訳し、さらに証明もコンパクトなも…

単位円上の有理点のなす群と、p=a²+b²の形に表せる素数

単位円上の有理点のなす群と、p=a^2+b^2の形に表せる素数 本記事では、単位円上の有理点のなす群\rm SO(\mathbb Q)を考察します。単位円上の有理点は、「ピタゴラスの三つ組」、つまり a^2+b^2=c^2 を充たす(a,b,c) \in \mathbb Z^3の全体の、定数倍を同一視…

Nimのインストール

NimはPythonのような文法を持つ静的型付け言語です。実際使ってみるとPythonの皮を被ったCって感じです。 まだ日本語の記事が少ない(2021/4)ので、こちらでインストール方法を紹介します。 choosenim のインストール Nimをインストール標準的な方法はNimの…

セグレ埋め込みと射影多様体の積(2)~代数幾何学~

セグレ埋め込みと射影多様体の積(1)~代数幾何学~ https://jijtech.hatenablog.com/entry/2020/11/13/105951 から続きます。 射影多様体の積 いよいよ、射影代数多様体の積を定義します。任意の準射影多様体X \sub \mathbb P^n及びY\sub \mathbb P^mにつ…

航空機荷物搭載最適化問題

この記事の概要 Pilon et al., 2021, "Aircraft Loading Optimization - QUBO models under multiple constraints"を読み、その理解を深めるために内容をまとめたものです。 この記事の概要 Aircraft Loading Optimization モデル化 目的関数 制約 Payload L…

ポケモン最適化 Vol. 1: 1 vs 1

Jij meets Pokemon. この記事の概要 任天堂の大人気ゲーム「ポケットモンスター」を最適化問題として定式化し、それをOpenJijで解いてみようという趣旨の記事です。 この記事の概要 序章(先行研究) 逃げるんじゃねぇ!サシで勝負だ! 定式化 バイナリ変数 制…

セグレ埋め込みと射影多様体の積(1)~代数幾何学~

セグレ埋め込みと射影多様体の積(1)~代数幾何学~ ここでは、射影多様体同士の積を定義するために必要な、セグレ埋め込みを考察します。セグレ埋め込みとは大雑把に言えば、二つの射影多様体の直積集合を次元の大きい射影空間に埋め込んで、誘導位相を入…

「ナップサック問題が量子アニーリング(QA)で解けない」は本当か?

この記事の概要 Pusey-Nazaro & Date, 2020, "Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem"を読み、実際にその内容を検証・考察したものです。 この記事の概要 ナップサック問題 概要 定式化 制約: ナップサックで運ぶことができる…

量子コンピュータでLHC高エネルギー実験データ探索

この記事の概要 Armenakas & Baker, 2020, "Application of a Quantum Search Algorithm to High-Energy Physics Data at the Large Hadron Collider"を読んだので、その理解を深めるためのアウトプットとして作成したものです。 この記事の概要 序章: Grove…

代数幾何の考え方 其の二

準同型写像と準同型定理 代数学で基本的な概念であり、色々なことを証明する時に空気のように使われる道具でもある、準同型写像について軽く触れておきましょう。環の準同型とは、直感的に言えば環の和と積の構造を保ったまま別の環に埋め込む(単射とは限り…

代数幾何の考え方 其の一

代数幾何とは、大雑把に言えば図形を代数学の言葉で扱う分野です。しかし、図形を代数の言語で扱って良いことを保証するための準備(特にヒルベルトの零点定理)に辿り着くまでにはそれなりに代数学、特に可換環論の知識が必要です。 本記事では、厳密さに…

超伝導量子ビットによるダークマター探査

この記事の概要 この記事はDixit et al., 2020, "Searching for Dark Matter with a Superconducting Qubit"を読んだので、その理解を深めるためのアウトプットとして作成されたものです。 この記事の概要 序章: ダークマターとは 概要 観測の歴史 銀河団に…

断熱量子計算によるHHLアルゴリズム

この記事の概要 Subasi et al., 2018, "Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing"を読んだので、その理解を深めるためのアウトプットとして作成したものです。 この記事の概要 問題設定 断熱量子計算 …

有理数と実数の構成から、可換環論をのぞき見してみる

本記事は、数学のごく基本的な知識(集合の素朴な定義、同値関係と商集合、コーシー列)を知っておけば読めるようになっています。 まず、整数環\Zは定義済みとして考えましょう。厳密に言えば、\Zはペアノの公理という公理から定義されるものなのですが、そ…

Capacitive-shunted flux qubitを用いた量子アニーリング

この記事の概要 この記事はMatsuzaki et al., 2020, "Quantum annealing with capacitive-shunted flux qubits"の理解を深めるためのアウトプットとして作成されたものです。 この記事の概要 Capacity-Shunted Flux Qubits (CSFQ) 構成回路図 エネルギー準位…

ヒルベルト空間のテンソル積に関する数学的に厳密な説明

ヒルベルト空間のテンソル積の数学的に厳密な説明html {overflow-x: initial !important;}:root { --bg-color:#ffffff; --text-color:#333333; --select-text-bg-color:#B5D6FC; --select-text-font-color:auto; --monospace:"Lucida Console",Consolas,"Cou…

直感的「環・加群入門」

直感的「環・加群入門」html {overflow-x: initial !important;}:root { --bg-color:#ffffff; --text-color:#333333; --select-text-bg-color:#B5D6FC; --select-text-font-color:auto; --monospace:"Lucida Console",Consolas,"Courier",monospace; } html …

IBMのNISQデバイスでK-Meansクラスタリング

この記事の概要 この記事はKhan et al., 2019, "K-Means Clustering on Noisy Intermediate Scale Quantum Computers"を読んだので、その理解を深めるためのアウトプットとして作成したものです。 この記事の概要 この論文の概要 関連した話題 基本的な量子K…

リーマン面入門

リーマン面入門html {overflow-x: initial !important;}:root { --bg-color:#ffffff; --text-color:#333333; --select-text-bg-color:#B5D6FC; --select-text-font-color:auto; --monospace:"Lucida Console",Consolas,"Courier",monospace; } html { font-…

距離指標に基づいた分類器の量子回路実装

この記事の概要 この記事はShuld et al., 2017, "Implementing a distance-based classifier with a quantum interference circuit"を読んだので、その理解を深めるためのアウトプットとして作成したものです。 距離に基づいた分類器 教師データセットがのよ…

量子回路でK-Meansクラスタリング

この記事の概要 2019年9月にarXivに投稿された論文、Khan et al., "K-Means Clustering on Noisy Intermediate Scale Quantum Computers"を読むための前提知識を学習するために作成した記事です。 この記事の概要 序章: K-Means法 アルゴリズム 計算量 量子K…

断熱量子線形回帰

この記事の概要 2020年8月5日に投稿された論文、Date & Potok, "Adiabatic Quantum Linear Regression"を読んだので、その内容の理解を深めるためにアウトプットしたものです。 この記事の概要 序章: 線形回帰 QUBO化 精度ベクトル バイナリ変数 QUBO化 数値…

量子アニーリングを用いた幾何学圧縮の最適化

この記事の概要 2020年3月に投稿されたFeld et al., "Optimizing Geometry Compression using Quantum Annealing"を読んだので、その理解を深めるためにアウトプットしたものです。 この記事の概要 論文概要 背景 CSG木と抽出問題 関連研究 CSG木の抽出問題 …

Wishart Planted Ensemble (WPE)

はじめに 本記事はJijにてインターンとして勤務してくださっている方が中心となって書いた記事です。 概要 組合せ最適化問題のような難しいとされる問題が与えられたとき、その問題を(近似的にでも)解く手法の開発は言うまでもありませんが非常に重要です。…

平面超伝導プロセッサにおける非平面グラフ問題の量子近似最適化

この記事の概要 2020年4月にGoogle AI Quantum and CollaboratorsがarXivに投稿した論文 "Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor" を読んだので、その理解を深めるためにアウトプットをした…

Adiabatic PageRank algorithm

この記事の概要 Googleのページ検索において重要な技術にページランクアルゴリズムがあります。この記事はその概要と、そのページランクを断熱量子計算で高速に求める手法をご紹介します。 この記事の概要 Google行列 ページ間リンク イテレーションによるペ…

IBMのNISQデバイスで量子振幅推定アルゴリズム -数値積分による実証-

この記事の概要 2020年8月4日に投稿された、Rao et al. "Quantum amplitude estimation algorithms on IBM quantum devices"を読んだのでその理解を深めるためにアウトプットしたものです。 この記事の概要 量子回路で数値積分する方法 演算子と数値積分 量…

最尤推定法による量子振幅推定

この記事の概要 2019年4月にarXivに投稿された論文のSuzuki et al. "Amplitude Estimation without Phase Estimation"を読み、その理解を深めるためにまとめたものです。 この記事の概要 量子振幅増幅 最尤推定法による量子振幅推定 数式による説明 図を用い…

1量子ビットに対するユニタリ演算がブロッホ球に於ける回転で解釈できることの数学的に厳密な説明

ブロッホ回転html {overflow-x: initial !important;}:root { --bg-color:#ffffff; --text-color:#333333; --select-text-bg-color:#B5D6FC; --select-text-font-color:auto; --monospace:"Lucida Console",Consolas,"Courier",monospace; } html { font-siz…