Com­bi­na­to­r­i­al opti­miza­tion prob­lems (COPs) have appli­ca­tions in many dif­fer­ent fields such as logis­tics, sup­ply chain man­age­ment, machine learn­ing, mate­r­i­al design and drug dis­cov­ery, among oth­ers, for find­ing the opti­mal solu­tion to com­plex prob­lems. These prob­lems are usu­al­ly very com­pu­ta­tion­al­ly inten­sive using clas­si­cal com­put­ers and thus solv­ing COPs using quan­tum com­put­ers has attract­ed sig­nif­i­cant atten­tion from both acad­e­mia and indus­try.

Quan­tum com­put­ers take advan­tage of the quan­tum prop­er­ty of super­po­si­tion, using spe­cial­ized qubits, that can exist in an infi­nite yet con­tained num­ber of states of 0 or 1 or any com­bi­na­tion of the two, to quick­ly solve large prob­lems. How­ev­er, when COPs involve con­straints, con­ven­tion­al quan­tum algo­rithms like adi­a­bat­ic quan­tum anneal­ing strug­gle to obtain a near-opti­mal solu­tion with­in the oper­a­tion time of quan­tum com­put­ers.

Recent advances in quan­tum tech­nol­o­gy have led to devices such as quan­tum anneal­ers and gate-type quan­tum devices that pro­vide suit­able plat­forms for solv­ing COPs. Unfor­tu­nate­ly, they are sus­cep­ti­ble to noise, which lim­its their applic­a­bil­i­ty to quan­tum algo­rithms with low com­pu­ta­tion­al costs.

To address this chal­lenge, Assis­tant Pro­fes­sor Tat­suhiko Shi­rai and Pro­fes­sor Nozomu Togawa from the Depart­ment of Com­put­er Sci­ence and Com­mu­ni­ca­tions Engi­neer­ing at Wase­da Uni­ver­si­ty in Japan have recent­ly devel­oped a post-pro­cess­ing vari­a­tion­al­ly sched­uled quan­tum algo­rithm (pVSQA). Their study was pub­lished in the jour­nal IEEE Trans­ac­tions on Quan­tum Engi­neer­ing.

“The two main meth­ods for solv­ing COPs with quan­tum devices are vari­a­tion­al sched­ul­ing and post-pro­cess­ing. Our algo­rithm com­bines vari­a­tion­al sched­ul­ing with a post-pro­cess­ing method that trans­forms infea­si­ble solu­tions into fea­si­ble ones, allow­ing us to achieve near-opti­mal solu­tions for con­strained COPs on both quan­tum anneal­ers and gate-based quan­tum com­put­ers,” explains Dr. Shi­rai.

The inno­v­a­tive pVSQA algo­rithm uses a quan­tum device to first gen­er­ate a vari­a­tion­al quan­tum state via quan­tum com­pu­ta­tion. This is then used to gen­er­ate a prob­a­bil­i­ty dis­tri­b­u­tion func­tion which con­sists of all the fea­si­ble and infea­si­ble solu­tions that are with­in the con­straints of the COP.

Next, the post-pro­cess­ing method trans­forms the infea­si­ble solu­tions into fea­si­ble ones, leav­ing the prob­a­bil­i­ty dis­tri­b­u­tion with only fea­si­ble solu­tions. A clas­si­cal com­put­er is then used to cal­cu­late an ener­gy expec­ta­tion val­ue of the cost func­tion using this new prob­a­bil­i­ty dis­tri­b­u­tion. Repeat­ing this cal­cu­la­tion results in a near-opti­mal solu­tion.

The researchers ana­lyzed the per­for­mance of this algo­rithm using both a sim­u­la­tor and real quan­tum devices such as a quan­tum anneal­er and a gate-type quan­tum device. The exper­i­ments revealed that pVSQA achieves a near-opti­mal per­for­mance with­in a pre­de­ter­mined time on the sim­u­la­tor and out­per­forms con­ven­tion­al quan­tum algo­rithms with­out post-pro­cess­ing on real quan­tum devices.

Dr. Shi­rai said, “Dras­tic social trans­for­ma­tions are urgent­ly need­ed to address var­i­ous social issues. Exam­ples include the real­iza­tion of a car­bon-neu­tral soci­ety to solve cli­mate change issues and the real­iza­tion of sus­tain­able devel­op­ment goals to address issues such as increased ener­gy demand and food short­age.

“Effi­cient­ly solv­ing com­bi­na­to­r­i­al opti­miza­tion prob­lems is at the heart of achiev­ing these trans­for­ma­tions. Our new method will play a sig­nif­i­cant role in real­iz­ing these long-term social trans­for­ma­tions.”

In con­clu­sion, this study marks a sig­nif­i­cant step for­ward for using quan­tum com­put­ers for solv­ing COPs, hold­ing promise for address­ing com­plex real-world prob­lems across var­i­ous domains.