色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
电子发烧友
开通电子发烧友VIP会员 尊享10大特权
海量资料免费下载
精品直播免费看
优质内容免费畅学
课程9折专享价
創(chuàng)作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內(nèi)不再提示

一文了解如何應用QUBO模型來建模

玻色量子 ? 來源:玻色量子 ? 2023-04-06 14:19 ? 次閱讀
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

Ising模型與QUBO模型

1.伊辛模型(Ising Model)

相干伊辛機(Coherent Ising Machine, 簡稱CIM), 是目前玻色量子重點研發(fā)的一項光量子計算機技術,CIM是一種基于簡并光學參量振蕩器(DOPO)的光量子計算機,在數(shù)學實踐中, 我們可以將其抽象為優(yōu)化Ising模型的專用計算機。

Ising模型是一類描述物質(zhì)相變的隨機過程模型。抽象為數(shù)學形式為:

a81ed8f4-d42a-11ed-bfe3-dac502259ad0.png

其中σ為待求自旋變量, 取值為{+1,-1},H為哈密頓量,J和μ分別為二次項系數(shù)、線性項系數(shù), 是已知量。

2.區(qū)分

QUBO模型更便于建模,Ising模型可以用于CIM求解器直接求解。同時,QUBO模型和Ising模型之間可以互相轉(zhuǎn)化。

1)變量代換

a834185e-d42a-11ed-bfe3-dac502259ad0.png

2)創(chuàng)建輔助變量完成一次項轉(zhuǎn)化

QUBO模型建模秘籍

一、什么是組合優(yōu)化問題?

組合優(yōu)化(Combinatorial Optimization, CO)領域是優(yōu)化領域中最重要的領域之一,它也是運籌學、計算機科學和分析學研究團體所追求的最活躍的研究領域之一。

組合優(yōu)化是在一個有限的對象集中找出最優(yōu)對象的一類問題。組合優(yōu)化的問題特征是可行解的集是離散或者可以簡化到離散的,目標是找到最優(yōu)解。常見的例子有數(shù)字劃分問題、旅行商問題等。

一般來說,這些問題涉及在必須做出大量是/否決策的情況下做出明智的選擇,并且每一組決策都會產(chǎn)生相應的目標函數(shù)值,例如成本或利潤值。然而在這些環(huán)境中找到好的解決方案是極其困難的。

而QUBO建模方式可以包含在工業(yè)、科學和政府中發(fā)現(xiàn)的各種重要CO問題,借助QUBO求解器的求解能力可以有效地幫助解決許多重要問題。

二、什么是QUBO模型?

QUBO(QuadraticUnconstrained Binary Optimizatoin),無約束二次二進制優(yōu)化模型是現(xiàn)在量子計算中應用最廣泛的優(yōu)化模型,它統(tǒng)一了豐富多樣的組合優(yōu)化問題。

隨著問題規(guī)模的增加,利用傳統(tǒng)方法求解該問題,求解時間會變得不可接受,但利用QUBO模型可以通過量子計算機加速,高效求解組合優(yōu)化問題。同時,QUBO模型可以表達位運算,進而表達各種邏輯,操作簡便,具體形式如下。

1.基礎QUBO形式:minimize/maximize

a84d32ee-d42a-11ed-bfe3-dac502259ad0.png

Q為QUBO矩陣,x為二進制變量組成的向量,每個變量取值均為{0,1},QUBO目標為找到使得y最小或最大的x

其中,Q矩陣的形式有2種:

1)對稱形式

a8620746-d42a-11ed-bfe3-dac502259ad0.png

2)上三角形式

a8737d96-d42a-11ed-bfe3-dac502259ad0.png

舉例:

a888653a-d42a-11ed-bfe3-dac502259ad0.png

a8996e34-d42a-11ed-bfe3-dac502259ad0.png

2.位運算

a8acfd28-d42a-11ed-bfe3-dac502259ad0.png

與 同時為1,結(jié)果才為1;

或 同時為0,結(jié)果才為0;

非0變成1,1變成0;

異或 兩位相同為0,相異為1

位運算表達

a8bec2ec-d42a-11ed-bfe3-dac502259ad0.png

a8ceb97c-d42a-11ed-bfe3-dac502259ad0.png

a8df9206-d42a-11ed-bfe3-dac502259ad0.png

a8f628c2-d42a-11ed-bfe3-dac502259ad0.png

a90aef78-d42a-11ed-bfe3-dac502259ad0.png

3.添加約束條件

舉例1:

a91f31a4-d42a-11ed-bfe3-dac502259ad0.png

通過添加約束項,并設置較大的系數(shù)P保證約束內(nèi)容的優(yōu)先級。

舉例2:

a933d398-d42a-11ed-bfe3-dac502259ad0.png

a949f31c-d42a-11ed-bfe3-dac502259ad0.png

約束條件舉例

a95cbde4-d42a-11ed-bfe3-dac502259ad0.png? ? ?

4.整數(shù)表達

a972693c-d42a-11ed-bfe3-dac502259ad0.png

通過二進制表達整數(shù),使用d個變量可以表達0到2^d ?1 的數(shù)字。

舉例:

a98552f4-d42a-11ed-bfe3-dac502259ad0.png

a9973870-d42a-11ed-bfe3-dac502259ad0.png

5.不等式約束

a9abc22c-d42a-11ed-bfe3-dac502259ad0.png

不等式約束可以轉(zhuǎn)化為等式約束,通過松弛變量y表示出不等式兩邊的差。

a9be13a0-d42a-11ed-bfe3-dac502259ad0.png

其中y為通過二進制表達的整數(shù),構(gòu)造約束項:

a9d1bfae-d42a-11ed-bfe3-dac502259ad0.png

(注意點:這樣做會引入新的變量,增加問題規(guī)模)

6.擴展思考

HOBO問題(High Order Binary Optimization),是指用二次多項式難以表達的高次問題。對于高次的問題,可以將x1x2替換為y,并添加約束項使得x1x2=y,從而將高次的問題轉(zhuǎn)化為二次優(yōu)化問題。

約束項:Rosenberg多項式

a9e6ff0e-d42a-11ed-bfe3-dac502259ad0.png

滿足:

aa023652-d42a-11ed-bfe3-dac502259ad0.png

(注意點:這樣做會引入新的變量,增加問題規(guī)模)

三、QUBO可以解決哪些問題?

最大獨立集問題

不對稱分配問題

對稱分配問題

邊約束分配問題

二次背包問題

最大團問題

最大割問題

整數(shù)劃分問題

旅行商問題

舉例1:整數(shù)劃分問題

1)整數(shù)劃分問題(The Number Partitioning Problem),NP-complete將包含n個非負整數(shù)的數(shù)集劃分為兩個子集,使這兩個子集的和盡可能接近

aa1c2db4-d42a-11ed-bfe3-dac502259ad0.png

設數(shù)集為

aa2c86fa-d42a-11ed-bfe3-dac502259ad0.png

選兩個子集滿足,使得下值最小

aa465472-d42a-11ed-bfe3-dac502259ad0.png

舉例S= {1,2,3,4,8},一組最有解為S1= {1,8} S2={2,3,4}是一組最優(yōu)解,兩者的和均為9

2)整數(shù)劃分問題建模思路

1. 定義決策變量,決定每個整數(shù)被分到哪一個集合

2. 使用決策變量表達出兩個集合整數(shù)和的差值

3. 通過CIM優(yōu)化目標函數(shù),得到最小值對應的解

3)整數(shù)劃分問題建模過程

定義決策變量xi,xi=1表示 Si∈S1,xi=0表示Si∈S2

兩個子集求和的差值:

aa5b4580-d42a-11ed-bfe3-dac502259ad0.png

目標函數(shù):

aa731f0c-d42a-11ed-bfe3-dac502259ad0.png

其中,

aa875094-d42a-11ed-bfe3-dac502259ad0.png

舉例2:旅行商問題

1)旅行商問題(Traveling Salesman Problem)NP-Complete,商人想要在地圖上走完所有城市,每個城市只經(jīng)過一次,最后回到最初的城市,求路程最短的走法。

給定帶權圖G(V,E),V為點集,E為邊集,要求遍歷所有點再回到初始點,求路程最短的走法。哈密頓回路:遍歷所有點再回到初始點。

舉例:

aaa0b138-d42a-11ed-bfe3-dac502259ad0.png

2)旅行商問題建模思路1.0

以下圖為例,定義決策變量xi,u,表示“經(jīng)過的第i個節(jié)點為u”是否為真,通過決策變量表達出距離,再通過添加約束條件使得求解方案能夠成立,構(gòu)造得到表達式通過CIM進行優(yōu)化。

目標包括:

1. 路程最小

2. 路線為環(huán)(約束自然滿足)

3. 同時只能經(jīng)過一個節(jié)點(約束)

4. 每個點經(jīng)過次數(shù)為1(約束)

5. 不能走不存在的連接(約束)

aabdd3bc-d42a-11ed-bfe3-dac502259ad0.png

3)旅行商問題建模過程

設有n個節(jié)點,wu,v從u到v的邊的邊權,定義決策變量xi,u,表示“經(jīng)過的第i個節(jié)點為u”是否為真,路程為環(huán)可以根據(jù)決策變量的定義自然滿足,則經(jīng)過的路程可以表達為:

aadb4974-d42a-11ed-bfe3-dac502259ad0.png

aaf115e2-d42a-11ed-bfe3-dac502259ad0.png

4)旅行商問題約束條件

為使得xi,u符合實際情況,需要如下約束:

第i個節(jié)點只有一個節(jié)點

ab0b56c8-d42a-11ed-bfe3-dac502259ad0.png

節(jié)點u只在路線中出現(xiàn)一次

ab200794-d42a-11ed-bfe3-dac502259ad0.png

可以根據(jù)以上兩個條件構(gòu)造約束

ab34206c-d42a-11ed-bfe3-dac502259ad0.png

為了保證不存在的邊不出現(xiàn)在方案中設置約束項

ab49d0ba-d42a-11ed-bfe3-dac502259ad0.png

P為懲罰項系數(shù),取值需要顯著大于其他邊權,最終的約束項:

ab5f7780-d42a-11ed-bfe3-dac502259ad0.png

目標函數(shù)包括回路總長和約束兩部分:

ab77a198-d42a-11ed-bfe3-dac502259ad0.png

2)旅行商問題建模思路2.0

定義決策變量xu,v,表示“使用u到v的邊”,通過決策變量表達出距離,再通過添加約束條件使得求解方案能夠成立,構(gòu)造得到表達式通過CIM進行優(yōu)化。

目標包括:

1. 路程最小

2. 每個點出發(fā)一次(約束)

3. 到達每個點一次(約束)

4. 不能走不存在的連接(約束)

aba4892e-d42a-11ed-bfe3-dac502259ad0.png

由于相干光量子計算最擅長攻克組合優(yōu)化問題,可應用賦能場景廣泛,如金融業(yè)的投資組合優(yōu)化、資本風險分析建模;生物制藥業(yè)的蛋白質(zhì)折疊、小分子組合和DNA重組;

交通物流行業(yè)路徑優(yōu)化等,這些都是在實際工作中經(jīng)常遇見的復雜度很高且計算量巨大的常規(guī)問題,所以該技術路線高度貼合市場需求,普適率高。






審核編輯:劉清

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學習之用,如有內(nèi)容侵權或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • CIM
    CIM
    +關注

    關注

    1

    文章

    88

    瀏覽量

    15613
  • 求解器
    +關注

    關注

    0

    文章

    79

    瀏覽量

    4724
  • 光量子計算機

    關注

    0

    文章

    11

    瀏覽量

    1736

原文標題:玻色量子真機體驗|一文了解如何應用QUBO模型來建模

文章出處:【微信號:玻色量子,微信公眾號:玻色量子】歡迎添加關注!文章轉(zhuǎn)載請注明出處。

收藏 2人收藏
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

  • jf_485911831

評論

相關推薦
熱點推薦

什么是數(shù)學建模,怎樣建立數(shù)學模型

什么是數(shù)學建模,怎樣建立數(shù)學模型 
發(fā)表于 09-15 12:53

網(wǎng)絡中心戰(zhàn)構(gòu)建模型是什么?

網(wǎng)絡中心戰(zhàn)理論是人們對歷史上信息和戰(zhàn)爭之間不解之緣深化認識的具體體現(xiàn)。眾所周知,空間和時間是軍事行動中兩個非常重要的要素,而網(wǎng)絡可以很好地聯(lián)系這兩個要素,因此隨著網(wǎng)絡技術的發(fā)展,網(wǎng)絡中心戰(zhàn)構(gòu)建模型
發(fā)表于 10-23 06:04

如何使用Patsy創(chuàng)建模型描述?

《利用Python進行數(shù)據(jù)分析》132 使用Patsy創(chuàng)建模型描述
發(fā)表于 07-14 07:50

你會用浩辰3D軟件進行零件建模嗎?

中的說明指導您完成特征構(gòu)造過程。3、構(gòu)造附加特征浩辰3D軟件附加特征基于您所繪制的草圖,這些3D特征可修改模型上現(xiàn)有的邊;或者可以基于您所指定的組屬性。例如,可繪制附加草圖,然后使用“選擇”工具
發(fā)表于 09-08 16:26

資料下載:基于MATLAB的風電場建模仿真研究牛步柯

(www.woc88.com)數(shù)億檔庫存里搜索。1、是描述風速的特性。在電力系統(tǒng)動態(tài)分析中,通常用它實現(xiàn)系統(tǒng)在較大風速變化情況下的動態(tài)性能。圖風電場詳細模型風電場模型仿真的風電場詳
發(fā)表于 07-06 08:00

如何使用Simscape Multibody的物理建模模塊建立倒立擺模型

Multibody的物理建模模塊建立倒立擺模型。Simscape庫中的塊代表實際的物理組件;因此,可以構(gòu)建復雜的多體動力學模型,而無需通過物理原理
發(fā)表于 07-07 06:16

分享種comsol磁場與結(jié)構(gòu)場耦合模型建模

的專業(yè)知識,無需在意,不求甚解主要學習本專業(yè)的建模,要及時補充專業(yè)知識、了解相關知識(指些術語、名詞)遇到問題難以理解的,且暫時沒能解決,先記住,以后遇到再深究COMSOL學習自學(孤家寡人),主要學習磁場與結(jié)構(gòu)場耦合
發(fā)表于 07-09 06:40

模型預測控制介紹

這篇主要講模型預測控制,如果對PID控制了解的同學,那效果更好。如果不了解PID控制,還是熟悉下比較好。模型預測控制,顧名思義,基于
發(fā)表于 08-18 06:21

求助,為pwm性能建模,想為驅(qū)動級找到個spice模型

我正在為 pwm 性能建模,想為驅(qū)動級找到個 spice 模型——謝謝……
發(fā)表于 01-16 08:48

基于ARMA模型和狼群算法的陀螺隨機漂移建模研究_凌紅

基于ARMA模型和狼群算法的陀螺隨機漂移建模研究_凌紅
發(fā)表于 03-19 19:07 ?3次下載

建立計算模型預測個給定博的抱怨強度

在計算語言學中,先前的研究主要集中在建立自動分類模型識別抱怨是否存在。Jin提供了個數(shù)據(jù)集,基于語用學注釋了不同嚴重程度的抱怨博
的頭像 發(fā)表于 11-08 09:54 ?836次閱讀

了解 PCB 的有效導熱系數(shù)

了解 PCB 的有效導熱系數(shù)
的頭像 發(fā)表于 11-24 15:48 ?2841次閱讀
<b class='flag-5'>一</b><b class='flag-5'>文</b><b class='flag-5'>了解</b> PCB 的有效導熱系數(shù)

了解剛?cè)峤Y(jié)合制造過程

了解剛?cè)峤Y(jié)合制造過程
的頭像 發(fā)表于 12-04 16:22 ?1201次閱讀

帶你了解 DAC

了解 DAC
的頭像 發(fā)表于 12-07 15:10 ?1.2w次閱讀
<b class='flag-5'>一</b><b class='flag-5'>文</b>帶你<b class='flag-5'>了解</b> DAC

arma-garch模型建模步驟

ARMA-GARCH模型種常用于金融市場時間序列數(shù)據(jù)的建模方法,它結(jié)合了自回歸移動平均(ARMA)模型和廣義自回歸條件異方差(GARCH)模型
的頭像 發(fā)表于 07-09 10:20 ?1676次閱讀
主站蜘蛛池模板: 武侠古典久久亚洲精品 | SAO货腿张开JI巴CAO死我 | 欧美日韩综合一区 | 日韩视频在线观看 | YELLOW免费观看完整视频 | 啪啪后入内射日韩 | 中文字幕一区二区三区在线播放 | 女人被躁到高潮嗷嗷叫小 | 99久久精品国产交换 | 狠狠综合久久综合88亚洲 | 欧美91精品久久久久网免费 | 国产精品VIDEOSSEX久久发布 | 欧美激情久久久久久久大片 | 国产东北男同志videos网站 | 中文字幕免费视频精品一 | 他揉捏她两乳不停呻吟口述 | 国产一区日韩二区欧美三区 | 亚洲AV久久久久久久无码 | 99视频精品免视3 | 亚洲色欲色欲WWW在线丝 | 窝窝影院午夜看片毛片 | 日韩少妇爆乳无码专区 | 久久亚洲精品2017 | 最新快播网站 | 国产电影尺度 | 99久久精品免费看国产免费 | jizzhd中国| 国产专区青青草原亚洲 | 美国特级成人毛片 | 我与旗袍老师疯狂床震 | 国产高清视频免费在线观看 | 国产亚洲精品久久久999密臂 | 久久WWW免费人成一看片 | 中文无码有码亚洲 欧美 | 婷婷六月激情综合一区 | 国产永久免费视频 | 儿子你得太大了慢点插 | 男人把女人桶到爽免费看视频 | 九色终合九色综合88 | 蜜臀AV99无码精品国产专区 | 久久www99re在线播放 |

電子發(fā)燒友

中國電子工程師最喜歡的網(wǎng)站

  • 2931785位工程師會員交流學習
  • 獲取您個性化的科技前沿技術信息
  • 參加活動獲取豐厚的禮品