Quadratic unconstrained binary optimization - Revision history

Rich Smith: CheckWiki Fixes (and other AWB fixes)

2025-06-23T12:17:07Z

CheckWiki Fixes (and other AWB fixes)

Smuecke1: added def with separate linear and quadratic terms

2025-06-23T09:20:43Z

added def with separate linear and quadratic terms

← Previous revision		Revision as of 09:20, 23 June 2025
Line 18:		Line 18:

	Let <math>\mathbb{B}=\lbrace 0,1\rbrace</math> the set of [[binary data\|binary]] digits (or <i>bits</i>), then <math>\mathbb{B}^n</math> is the set of binary vectors of fixed length <math>n\in\mathbb{N}</math>.		Let <math>\mathbb{B}=\lbrace 0,1\rbrace</math> the set of [[binary data\|binary]] digits (or <i>bits</i>), then <math>\mathbb{B}^n</math> is the set of binary vectors of fixed length <math>n\in\mathbb{N}</math>.
	Given a [[symmetric matrix\|symmetric]] upper [[triangular matrix]] <math>\boldsymbol Q\in\mathbb{R}^{n\times n}</math>, whose entries <math>Q_{ij}</math> define a weight for each pair of indices <math>i,j\in\lbrace 1,\dots,n\rbrace</math>, we can define the function <math>f_{\boldsymbol Q}: \mathbb{B}^n\rightarrow\mathbb{R}</math> that assigns a value to each binary vector <math>\boldsymbol x</math> through		Given a [[symmetric matrix\|symmetric]] or upper [[triangular matrix]] <math>\boldsymbol Q\in\mathbb{R}^{n\times n}</math>, whose entries <math>Q_{ij}</math> define a weight for each pair of indices <math>i,j\in\lbrace 1,\dots,n\rbrace</math>, we can define the function <math>f_{\boldsymbol Q}: \mathbb{B}^n\rightarrow\mathbb{R}</math> that assigns a value to each binary vector <math>\boldsymbol x</math> through
	: <math>f_{\boldsymbol Q}(\boldsymbol x) = \boldsymbol{x}^\intercal \boldsymbol{Qx} = \sum_{i=1}^n \sum_{j=1}^n Q_{ij} x_i x_j.</math>		: <math>f_{\boldsymbol Q}(\boldsymbol x) = \boldsymbol{x}^\intercal \boldsymbol{Qx} = \sum_{i=1}^n \sum_{j=1}^n Q_{ij} x_i x_j.</math>
			Alternatively, the linear and quadratic parts can be separated as
			: <math>f_{\boldsymbol Q',\boldsymbol q}(\boldsymbol x)=\boldsymbol x^\intercal\boldsymbol Q'\boldsymbol x+\boldsymbol q^\intercal\boldsymbol x,</math>
			where <math>\boldsymbol Q'\in\mathbb{R}^{n\times n}</math> and <math>\boldsymbol q\in\mathbb{R}^n</math>.
			This is equivalent to the previous definition through <math>\boldsymbol Q=\boldsymbol Q'+\operatorname{diag}[\boldsymbol q]</math> using the [[Diagonal matrix#Vector-to-matrix diag operator\|diag]] operator, exploiting that <math>x=x\cdot x</math> for all binary values <math>x</math>.

	Intuitively, the weight <math>Q_{ij}</math> is added if both <math>x_i=1</math> and <math>x_j=1</math>.		Intuitively, the weight <math>Q_{ij}</math> is added if both <math>x_i=1</math> and <math>x_j=1</math>.
	The QUBO problem consists of finding a binary vector <math>\boldsymbol{x}^</math> that minimizes <math>f_{\boldsymbol Q}</math>, i.e., <math>\forall\boldsymbol x\in\mathbb{B}^n: ~f_{\boldsymbol Q}(\boldsymbol{x}^)\leq f_{\boldsymbol Q}(\boldsymbol x)</math>.		The QUBO problem consists of finding a binary vector <math>\boldsymbol{x}^</math> that minimizes <math>f_{\boldsymbol Q}</math>, i.e., <math>\forall\boldsymbol x\in\mathbb{B}^n: ~f_{\boldsymbol Q}(\boldsymbol{x}^)\leq f_{\boldsymbol Q}(\boldsymbol x)</math>.

Smuecke1: Simplified notation for Max-Cut

2025-06-23T09:09:06Z

Simplified notation for Max-Cut

← Previous revision		Revision as of 09:09, 23 June 2025
Line 52:		Line 52:
	===Maximum Cut===		===Maximum Cut===

	Given a graph <math>G=(V,E)</math> with vertex set <math>V=\lbrace 1,\dots,n\rbrace</math> and edges <math>E\subseteq V\times V</math>, the [[maximum cut]] (max-cut) problem consists of finding two subsets <math>S,T\subseteq V</math> with <math>~~S\cap~~ T=\~~emptyset</math>~~ ~~and <math>~~S~~\cup T=V~~</math>, such that the number of edges between <math>S</math> and <math>T</math> is maximized.		Given a graph <math>G=(V,E)</math> with vertex set <math>V=\lbrace 1,\dots,n\rbrace</math> and edges <math>E\subseteq V\times V</math>, the [[maximum cut]] (max-cut) problem consists of finding two subsets <math>S,T\subseteq V</math> with <math>T=V\setminus S</math>, such that the number of edges between <math>S</math> and <math>T</math> is maximized.

	The more general <i>weighted max-cut</i> problem assumes a ~~weight function~~ <math>~~w:V^2\rightarrow\mathbb~~{R}_+</math> with <math>~~w(e)=0\text{ if }~~e\notin E</math>, and asks for a [[partition of a set\|partition]] <math>S,T\subseteq V</math> that maximizes the sum of edge weights between <math>S</math> and <math>T</math>, i.e.,		The more general <i>weighted max-cut</i> problem assumes edge weights <math>w_{ij}\geq 0~\forall i,j\in V</math>, with <math>e\notin E\Rightarrow w_{ij}=0</math>, and asks for a [[partition of a set\|partition]] <math>S,T\subseteq V</math> that maximizes the sum of edge weights between <math>S</math> and <math>T</math>, i.e.,
	: <math>\max_{S,T}\sum_{e\in S\~~times~~ T}~~w(e)~~.</math>		: <math>\max_{S,T}\sum_{i\in S, j\in T}w_{ij}.</math>
	By setting <math>~~w(e)~~=~~[e\in E]~~</math> ~~where~~ <math>[\~~cdot]~~</math> ~~denotes the [[Iverson bracket]]~~ this becomes equivalent to the original max-cut problem above, which is why we focus on this more general form in the following.		By setting <math>w_{ij}=1</math> for all <math>(i,j)\in E</math> this becomes equivalent to the original max-cut problem above, which is why we focus on this more general form in the following.

	For every vertex in <math>i\in V</math> we introduce a binary variable <math>x_i</math> with the meaning ''<math>x_i=0</math> if <math>i\in S</math>'' and ''<math>x_i=1</math> if <math>i\in T</math>''.		For every vertex in <math>i\in V</math> we introduce a binary variable <math>x_i</math> with the meaning ''<math>x_i=0</math> if <math>i\in S</math>'' and ''<math>x_i=1</math> if <math>i\in T</math>''.
Line 62:		Line 62:

	We observe that, for any <math>i,j\in V</math>, the expression <math>x_i(1-x_j)+(1-x_i)x_j</math> evaluates to 1 if and only if <math>i</math> and <math>j</math> are in different subsets.		We observe that, for any <math>i,j\in V</math>, the expression <math>x_i(1-x_j)+(1-x_i)x_j</math> evaluates to 1 if and only if <math>i</math> and <math>j</math> are in different subsets.
	Let <math>\boldsymbol W\in\mathbb{R}^{n\times n}_+</math> with <math>W_{ij}=~~w(i,j)</math>~~ ~~(recall that <math>w(i,j)=0</math> if <math>(~~i,j)\~~notin~~ E</math>).		Let <math>\boldsymbol W\in\mathbb{R}^{n\times n}_+</math> with <math>W_{ij}=w_{ij}~\forall i,j\in V</math>.
	By using above expression we find that		By using above expression we find that
		⚫	: <math>\boldsymbol x^\intercal\boldsymbol W(\boldsymbol 1-\boldsymbol x)+(\boldsymbol 1-\boldsymbol x)^\intercal\boldsymbol{Wx}=-2\boldsymbol x^\intercal\boldsymbol{Wx}+(\boldsymbol{W1}+\boldsymbol{W}^\intercal\boldsymbol 1)^\intercal\boldsymbol x</math>
	: <math>\begin{align}
⚫	\boldsymbol x^\intercal&\boldsymbol W(\boldsymbol 1-\boldsymbol x)+(\boldsymbol 1-\boldsymbol x)^\intercal\boldsymbol{Wx}\\
	&=-2\boldsymbol x^\intercal\boldsymbol{Wx}+(\boldsymbol{W1}+\boldsymbol{W}^\intercal\boldsymbol 1)^\intercal\boldsymbol x
	\end{align}</math>
	is the sum of weights of all edges between <math>S</math> and <math>T</math>, where <math>\boldsymbol 1=(1,1,\dots,1)^\intercal\in\mathbb{R}^n</math>.		is the sum of weights of all edges between <math>S</math> and <math>T</math>, where <math>\boldsymbol 1=(1,1,\dots,1)^\intercal\in\mathbb{R}^n</math>.
	As this function is quadratic in <math>\boldsymbol x</math>, it is a QUBO problem whose parameter matrix we can read from above expression as		As this function is quadratic in <math>\boldsymbol x</math>, it is a QUBO problem whose parameter matrix we can read from above expression as

Smuecke1: added Max-Cut as Application

2025-06-22T23:11:25Z

added Max-Cut as Application

@@ Line 49: / Line 49: @@
 QUBO is a structurally simple, yet computationally hard optimization problem.
 It can be used to encode a wide range of optimization problems from various scientific areas.<ref>{{cite web |url=https://blog.xa0.de/post/List-of-QUBO-formulations/ |title=List of QUBO formulations |last=Ratke |first=Daniel |date=2021-06-10 |access-date=2022-12-16}}</ref>
 ===Cluster Analysis===

Smuecke1: improved some wordings; clarified relation between Ising-QUBO and the physical Ising model

2025-06-18T09:24:43Z

improved some wordings; clarified relation between Ising-QUBO and the physical Ising model

Smuecke1: greatly simplified the notation for both the clustering example and the Ising conversion, using matrix vector notation

2025-06-18T00:14:06Z

greatly simplified the notation for both the clustering example and the Ising conversion, using matrix vector notation

Show changes

WikiOriginal-9: /* External links */

2025-06-08T00:22:24Z

External links

← Previous revision		Revision as of 00:22, 8 June 2025
Line 161:		Line 161:

	[[Category:Machine learning algorithms]]		[[Category:Machine learning algorithms]]


	{{compu-AI-stub}}

133.86.227.82: /* External links */

2024-12-24T05:16:31Z

External links

← Previous revision		Revision as of 05:16, 24 December 2024
Line 158:		Line 158:
	\| publisher = Elsevier		\| publisher = Elsevier
	}}		}}
			* [https://abs2.cs.hiroshima-u.ac.jp/ Hiroshima University and NTT DATA Group Corporation : "QUBO++ with ABS2 GPU QUBO Solver"] # Software.

	[[Category:Machine learning algorithms]]		[[Category:Machine learning algorithms]]

Zechenhund: https supplied for ref. 1

2024-10-25T08:46:32Z

https supplied for ref. 1

← Previous revision		Revision as of 08:46, 25 October 2024
Line 1:		Line 1:
	{{Short description\|Combinatorial optimization problem}}		{{Short description\|Combinatorial optimization problem}}
	<!-- {{refimprove\|date=September 2014}} -->		<!-- {{refimprove\|date=September 2014}} -->
	'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=~~http~~://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>		'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=https://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>
	Embeddings for machine learning models include [[support-vector machine\|support-vector machines]], [[cluster analysis\|clustering]] and [[probabilistic graphical model\|probabilistic graphical models]].<ref>{{cite journal \|last1=Mücke \|first1=Sascha \|last2=Piatkowski \|first2=Nico \|last3=Morik \|first3=Katharina \|author3-link=Katharina Morik\|title=Learning Bit by Bit: Extracting the Essence of Machine Learning \|journal=LWDA \|date=2019 \|s2cid=202760166 \|url=https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|archive-url=https://web.archive.org/web/20200227143739/https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|url-status=dead \|archive-date=2020-02-27 }}</ref>		Embeddings for machine learning models include [[support-vector machine\|support-vector machines]], [[cluster analysis\|clustering]] and [[probabilistic graphical model\|probabilistic graphical models]].<ref>{{cite journal \|last1=Mücke \|first1=Sascha \|last2=Piatkowski \|first2=Nico \|last3=Morik \|first3=Katharina \|author3-link=Katharina Morik\|title=Learning Bit by Bit: Extracting the Essence of Machine Learning \|journal=LWDA \|date=2019 \|s2cid=202760166 \|url=https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|archive-url=https://web.archive.org/web/20200227143739/https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|url-status=dead \|archive-date=2020-02-27 }}</ref>
	Moreover, due to its close connection to [[Ising model\|Ising models]], QUBO constitutes a central problem class for [[adiabatic quantum computing\|adiabatic quantum computation]], where it is solved through a physical process called [[quantum annealing]].<ref>{{cite web		Moreover, due to its close connection to [[Ising model\|Ising models]], QUBO constitutes a central problem class for [[adiabatic quantum computing\|adiabatic quantum computation]], where it is solved through a physical process called [[quantum annealing]].<ref>{{cite web

Uhai: Adding local short description: "Combinatorial optimization problem", overriding Wikidata description "combinatorial optimization problem"

2024-05-02T07:23:17Z

Adding local short description: "Combinatorial optimization problem", overriding Wikidata description "combinatorial optimization problem"

← Previous revision		Revision as of 07:23, 2 May 2024
Line 1:		Line 1:
			{{Short description\|Combinatorial optimization problem}}
	<!-- {{refimprove\|date=September 2014}} -->		<!-- {{refimprove\|date=September 2014}} -->
	'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=http://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>		'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=http://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>

← Previous revision		Revision as of 08:46, 25 October 2024
Line 1:		Line 1:
	{{Short description\|Combinatorial optimization problem}}		{{Short description\|Combinatorial optimization problem}}
	<!-- {{refimprove\|date=September 2014}} -->		<!-- {{refimprove\|date=September 2014}} -->
	'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=~~http~~://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>		'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=https://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>
	Embeddings for machine learning models include [[support-vector machine\|support-vector machines]], [[cluster analysis\|clustering]] and [[probabilistic graphical model\|probabilistic graphical models]].<ref>{{cite journal \|last1=Mücke \|first1=Sascha \|last2=Piatkowski \|first2=Nico \|last3=Morik \|first3=Katharina \|author3-link=Katharina Morik\|title=Learning Bit by Bit: Extracting the Essence of Machine Learning \|journal=LWDA \|date=2019 \|s2cid=202760166 \|url=https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|archive-url=https://web.archive.org/web/20200227143739/https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|url-status=dead \|archive-date=2020-02-27 }}</ref>		Embeddings for machine learning models include [[support-vector machine\|support-vector machines]], [[cluster analysis\|clustering]] and [[probabilistic graphical model\|probabilistic graphical models]].<ref>{{cite journal \|last1=Mücke \|first1=Sascha \|last2=Piatkowski \|first2=Nico \|last3=Morik \|first3=Katharina \|author3-link=Katharina Morik\|title=Learning Bit by Bit: Extracting the Essence of Machine Learning \|journal=LWDA \|date=2019 \|s2cid=202760166 \|url=https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|archive-url=https://web.archive.org/web/20200227143739/https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|url-status=dead \|archive-date=2020-02-27 }}</ref>
	Moreover, due to its close connection to [[Ising model\|Ising models]], QUBO constitutes a central problem class for [[adiabatic quantum computing\|adiabatic quantum computation]], where it is solved through a physical process called [[quantum annealing]].<ref>{{cite web		Moreover, due to its close connection to [[Ising model\|Ising models]], QUBO constitutes a central problem class for [[adiabatic quantum computing\|adiabatic quantum computation]], where it is solved through a physical process called [[quantum annealing]].<ref>{{cite web

← Previous revision		Revision as of 07:23, 2 May 2024
Line 1:		Line 1:
			{{Short description\|Combinatorial optimization problem}}
	<!-- {{refimprove\|date=September 2014}} -->		<!-- {{refimprove\|date=September 2014}} -->
	'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=http://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>		'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=http://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>

← Previous revision		Revision as of 12:17, 23 June 2025
Line 2:		Line 2:
	<!-- {{refimprove\|date=September 2014}} -->		<!-- {{refimprove\|date=September 2014}} -->
	'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=https://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>		'''Quadratic unconstrained binary optimization''' ('''QUBO'''), also known as '''unconstrained binary quadratic programming''' ('''UBQP'''), is a combinatorial [[optimization problem]] with a wide range of applications from [[finance]] and [[economics]] to [[machine learning]].<ref>{{cite journal \|last1=Kochenberger \|first1=Gary \|last2=Hao \|first2=Jin-Kao \|first3=Fred \|last3=Glover \|first4=Mark \|last4=Lewis \|first5=Zhipeng\|last5=Lu \|first6=Haibo \|last6=Wang \|first7=Yang \|last7=Wang \|title=The unconstrained binary quadratic programming problem: a survey. \|journal=Journal of Combinatorial Optimization \|date=2014 \|volume=28 \|pages=58–81 \|doi=10.1007/s10878-014-9734-0 \|s2cid=16808394 \|url=https://leeds-faculty.colorado.edu/glover/454%20-%20xQx%20survey%20article%20as%20published%202014.pdf}}</ref> QUBO is an [[NP hard]] problem, and for many classical problems from [[theoretical computer science]], like [[maximum cut]], [[graph coloring]] and the [[partition problem]], embeddings into QUBO have been formulated.<ref name="tut">{{cite arXiv \|last1=Glover \|first1=Fred \|last2=Kochenberger\|first2=Gary \|eprint=1811.11538 \|title=A Tutorial on Formulating and Using QUBO Models \|class= cs.DS\|date=2019 }}</ref><ref>{{cite journal \|last1=Lucas \|first1=Andrew \|title=Ising formulations of many NP problems \|journal=Frontiers in Physics \|date=2014 \|volume=2 \|page=5 \|doi=10.3389/fphy.2014.00005 \|arxiv=1302.5843 \|bibcode=2014FrP.....2....5L \|doi-access=free }}</ref>
	Embeddings for machine learning models include [[support-vector machine~~\|support-vector machines~~]], [[cluster analysis\|clustering]] and [[probabilistic graphical model~~\|probabilistic graphical models~~]].<ref>{{cite journal \|last1=Mücke \|first1=Sascha \|last2=Piatkowski \|first2=Nico \|last3=Morik \|first3=Katharina \|author3-link=Katharina Morik\|title=Learning Bit by Bit: Extracting the Essence of Machine Learning \|journal=LWDA \|date=2019 \|s2cid=202760166 \|url=https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|archive-url=https://web.archive.org/web/20200227143739/https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|url-status=dead \|archive-date=2020-02-27 }}</ref>		Embeddings for machine learning models include [[support-vector machine]]s, [[cluster analysis\|clustering]] and [[probabilistic graphical model]]s.<ref>{{cite journal \|last1=Mücke \|first1=Sascha \|last2=Piatkowski \|first2=Nico \|last3=Morik \|first3=Katharina \|author3-link=Katharina Morik\|title=Learning Bit by Bit: Extracting the Essence of Machine Learning \|journal=LWDA \|date=2019 \|s2cid=202760166 \|url=https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|archive-url=https://web.archive.org/web/20200227143739/https://pdfs.semanticscholar.org/f484/b4a789e1563b91a416a7cfabbf72f0aa3b2a.pdf \|url-status=dead \|archive-date=2020-02-27 }}</ref>
	Moreover, due to its close connection to [[Ising model~~\|Ising models~~]], QUBO constitutes a central problem class for [[adiabatic quantum computing\|adiabatic quantum computation]], where it is solved through a physical process called [[quantum annealing]].<ref>{{cite web		Moreover, due to its close connection to [[Ising model]]s, QUBO constitutes a central problem class for [[adiabatic quantum computing\|adiabatic quantum computation]], where it is solved through a physical process called [[quantum annealing]].<ref>{{cite web
	\|url = http://www.technologyreview.com/view/514686/d-waves-quantum-computer-goes-to-the-races-wins/		\|url = http://www.technologyreview.com/view/514686/d-waves-quantum-computer-goes-to-the-races-wins/
	\|title = D-Wave's Quantum Computer Goes to the Races, Wins		\|title = D-Wave's Quantum Computer Goes to the Races, Wins
Line 17:		Line 17:
	==Definition==		==Definition==

	Let <math>\mathbb{B}=\lbrace 0,1\rbrace</math> the set of [[binary data\|binary]] digits (or ~~<i>~~bits~~</i>~~), then <math>\mathbb{B}^n</math> is the set of binary vectors of fixed length <math>n\in\mathbb{N}</math>.		Let <math>\mathbb{B}=\lbrace 0,1\rbrace</math> the set of [[binary data\|binary]] digits (or ''bits''), then <math>\mathbb{B}^n</math> is the set of binary vectors of fixed length <math>n\in\mathbb{N}</math>.
	Given a [[symmetric matrix\|symmetric]] or upper [[triangular matrix]] <math>\boldsymbol Q\in\mathbb{R}^{n\times n}</math>, whose entries <math>Q_{ij}</math> define a weight for each pair of indices <math>i,j\in\lbrace 1,\dots,n\rbrace</math>, we can define the function <math>f_{\boldsymbol Q}: \mathbb{B}^n\rightarrow\mathbb{R}</math> that assigns a value to each binary vector <math>\boldsymbol x</math> through		Given a [[symmetric matrix\|symmetric]] or upper [[triangular matrix]] <math>\boldsymbol Q\in\mathbb{R}^{n\times n}</math>, whose entries <math>Q_{ij}</math> define a weight for each pair of indices <math>i,j\in\lbrace 1,\dots,n\rbrace</math>, we can define the function <math>f_{\boldsymbol Q}: \mathbb{B}^n\rightarrow\mathbb{R}</math> that assigns a value to each binary vector <math>\boldsymbol x</math> through
	: <math>f_{\boldsymbol Q}(\boldsymbol x) = \boldsymbol{x}^\intercal \boldsymbol{Qx} = \sum_{i=1}^n \sum_{j=1}^n Q_{ij} x_i x_j.</math>		: <math>f_{\boldsymbol Q}(\boldsymbol x) = \boldsymbol{x}^\intercal \boldsymbol{Qx} = \sum_{i=1}^n \sum_{j=1}^n Q_{ij} x_i x_j.</math>
Line 59:		Line 59:
	Given a graph <math>G=(V,E)</math> with vertex set <math>V=\lbrace 1,\dots,n\rbrace</math> and edges <math>E\subseteq V\times V</math>, the [[maximum cut]] (max-cut) problem consists of finding two subsets <math>S,T\subseteq V</math> with <math>T=V\setminus S</math>, such that the number of edges between <math>S</math> and <math>T</math> is maximized.		Given a graph <math>G=(V,E)</math> with vertex set <math>V=\lbrace 1,\dots,n\rbrace</math> and edges <math>E\subseteq V\times V</math>, the [[maximum cut]] (max-cut) problem consists of finding two subsets <math>S,T\subseteq V</math> with <math>T=V\setminus S</math>, such that the number of edges between <math>S</math> and <math>T</math> is maximized.

	The more general ~~<i>~~weighted max-cut~~</i>~~ problem assumes edge weights <math>w_{ij}\geq 0~\forall i,j\in V</math>, with <math>e\notin E\Rightarrow w_{ij}=0</math>, and asks for a [[partition of a set\|partition]] <math>S,T\subseteq V</math> that maximizes the sum of edge weights between <math>S</math> and <math>T</math>, i.e.,		The more general ''weighted max-cut'' problem assumes edge weights <math>w_{ij}\geq 0~\forall i,j\in V</math>, with <math>e\notin E\Rightarrow w_{ij}=0</math>, and asks for a [[partition of a set\|partition]] <math>S,T\subseteq V</math> that maximizes the sum of edge weights between <math>S</math> and <math>T</math>, i.e.,
	: <math>\max_{S,T}\sum_{i\in S, j\in T}w_{ij}.</math>		: <math>\max_{S,T}\sum_{i\in S, j\in T}w_{ij}.</math>
	By setting <math>w_{ij}=1</math> for all <math>(i,j)\in E</math> this becomes equivalent to the original max-cut problem above, which is why we focus on this more general form in the following.		By setting <math>w_{ij}=1</math> for all <math>(i,j)\in E</math> this becomes equivalent to the original max-cut problem above, which is why we focus on this more general form in the following.
Line 153:		Line 153:

	==External links==		==External links==

	*[http://plato.asu.edu/ftp/qubo.html QUBO Benchmark] (Benchmark of software packages for the exact solution of QUBOs; part of the well-known Mittelmann benchmark collection)		*[http://plato.asu.edu/ftp/qubo.html QUBO Benchmark] (Benchmark of software packages for the exact solution of QUBOs; part of the well-known Mittelmann benchmark collection)

	* {{cite journal		* {{cite journal
	\| url = http://portal.acm.org/citation.cfm?id=1231283		\| url = http://portal.acm.org/citation.cfm?id=1231283

← Previous revision		Revision as of 09:24, 18 June 2025
Line 18:		Line 18:

	Let <math>\mathbb{B}=\lbrace 0,1\rbrace</math> the set of [[binary data\|binary]] digits (or <i>bits</i>), then <math>\mathbb{B}^n</math> is the set of binary vectors of fixed length <math>n\in\mathbb{N}</math>.		Let <math>\mathbb{B}=\lbrace 0,1\rbrace</math> the set of [[binary data\|binary]] digits (or <i>bits</i>), then <math>\mathbb{B}^n</math> is the set of binary vectors of fixed length <math>n\in\mathbb{N}</math>.
	Given a [[symmetric matrix\|symmetric]] upper [[triangular matrix]] <math>\boldsymbol Q\in\mathbb{R}^{n\times n}</math>, whose entries <math>Q_{ij}</math> define a weight for each pair of indices <math>i,j\in\lbrace 1,\dots,n\rbrace</math> ~~within the binary vector~~, we can define the function <math>f_{\boldsymbol Q}: \mathbb{B}^n\rightarrow\mathbb{R}</math> that assigns a value to each binary vector <math>\boldsymbol x</math> through		Given a [[symmetric matrix\|symmetric]] upper [[triangular matrix]] <math>\boldsymbol Q\in\mathbb{R}^{n\times n}</math>, whose entries <math>Q_{ij}</math> define a weight for each pair of indices <math>i,j\in\lbrace 1,\dots,n\rbrace</math>, we can define the function <math>f_{\boldsymbol Q}: \mathbb{B}^n\rightarrow\mathbb{R}</math> that assigns a value to each binary vector <math>\boldsymbol x</math> through
	: <math>f_{\boldsymbol Q}(\boldsymbol x) = \boldsymbol{x}^\intercal \boldsymbol{Qx} = \sum_{i=1}^n \sum_{j=1}^n Q_{ij} x_i x_j.</math>		: <math>f_{\boldsymbol Q}(\boldsymbol x) = \boldsymbol{x}^\intercal \boldsymbol{Qx} = \sum_{i=1}^n \sum_{j=1}^n Q_{ij} x_i x_j.</math>
	Intuitively, the weight <math>Q_{ij}</math> is added if both <math>x_i=1</math> and <math>x_j=1~~</math> for all <math>i,j\in\lbrace 1,\dots,n\rbrace~~</math>.		Intuitively, the weight <math>Q_{ij}</math> is added if both <math>x_i=1</math> and <math>x_j=1</math>.
	The QUBO problem consists of finding a binary vector <math>\boldsymbol{x}^*</math> that is ~~minimal~~ ~~with~~ ~~respect to~~ <math>f_{\boldsymbol Q}</math>~~, namely~~		The QUBO problem consists of finding a binary vector <math>\boldsymbol{x}^</math> that minimizes <math>f_{\boldsymbol Q}</math>, i.e., <math>\forall\boldsymbol x\in\mathbb{B}^n: ~f_{\boldsymbol Q}(\boldsymbol{x}^)\leq f_{\boldsymbol Q}(\boldsymbol x)</math>.
	: <math>\forall\boldsymbol x\in\mathbb{B}^n: ~f_{\boldsymbol Q}(\boldsymbol{x}^*)\leq f_{\boldsymbol Q}(\boldsymbol x)</math>

	In general, <math>\boldsymbol{x}^*</math> is not unique, meaning there may be a set of minimizing vectors with equal value w.r.t. <math>f_{\boldsymbol Q}</math>.		In general, <math>\boldsymbol{x}^*</math> is not unique, meaning there may be a set of minimizing vectors with equal value w.r.t. <math>f_{\boldsymbol Q}</math>.
Line 99:		Line 98:
	QUBO is very closely related and computationally equivalent to the [[Ising model]], whose [[Hamiltonian function]] is defined as		QUBO is very closely related and computationally equivalent to the [[Ising model]], whose [[Hamiltonian function]] is defined as
	: <math>H(\boldsymbol\sigma) =\boldsymbol\sigma^\intercal \boldsymbol J\boldsymbol\sigma+\boldsymbol h^\intercal\boldsymbol\sigma =\sum_{i,j} J_{ij} \sigma_i \sigma_j +\sum_j h_j \sigma_j</math>		: <math>H(\boldsymbol\sigma) =\boldsymbol\sigma^\intercal \boldsymbol J\boldsymbol\sigma+\boldsymbol h^\intercal\boldsymbol\sigma =\sum_{i,j} J_{ij} \sigma_i \sigma_j +\sum_j h_j \sigma_j</math>
	with real-valued parameters <math>h_j, J_{ij}~~, \mu~~</math> for all <math>i,j</math>.		with real-valued parameters <math>h_j, J_{ij}</math> for all <math>i,j</math>.
	The ''spin variables'' <math>\sigma_j</math> are binary with values from <math>\lbrace -1,+1\rbrace</math> instead of <math>\mathbb{B}</math>.		The ''spin variables'' <math>\sigma_j</math> are binary with values from <math>\lbrace -1,+1\rbrace</math> instead of <math>\mathbb{B}</math>.
			Note that this formulation is simplified, since, in a physics context, <math>\sigma_i</math> are typically [[Pauli matrix\|Pauli operators]], which are complex-valued matrices of size <math>2^n\times 2^n</math>, whereas here we treat them as binary variables.
	~~Moreover,~~ in the Ising model the variables are ~~typically~~ arranged in a lattice where only neighboring pairs of variables <math>\langle i~j\rangle</math> can have non-zero coefficients.		Many formulations of the Ising model Hamiltonian further assume that the variables are arranged in a lattice, where only neighboring pairs of variables <math>\langle i~j\rangle</math> can have non-zero coefficients; here, we simply assume that <math>J_{ij}=0</math> if <math>i</math> and <math>j</math> are not neighbors.

	Applying the identity <math>\sigma = 1-2x</math> yields an equivalent QUBO problem <ref name="~~tut~~"/>		Applying the identity <math>\sigma = 1-2x</math> yields an equivalent QUBO problem <ref name="muecke2025"/>
	: <math>\begin{align}		: <math>\begin{align}
	&\boldsymbol\sigma^\intercal \boldsymbol J\boldsymbol\sigma+\boldsymbol h^\intercal\boldsymbol\sigma \\		&\boldsymbol\sigma^\intercal \boldsymbol J\boldsymbol\sigma+\boldsymbol h^\intercal\boldsymbol\sigma \\