{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T18:18:38Z","timestamp":1767896318445,"version":"3.49.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,5]]},"abstract":"<jats:p>The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases.<\/jats:p>\n          <jats:p>In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.<\/jats:p>","DOI":"10.14778\/2947618.2947621","type":"journal-article","created":{"date-parts":[[2016,7,26]],"date-time":"2016-07-26T13:28:39Z","timestamp":1469539719000},"page":"648-659","source":"Crossref","is-referenced-by-count":46,"title":["Multiple query optimization on the D-Wave 2X adiabatic quantum computer"],"prefix":"10.14778","volume":"9","author":[{"given":"Immanuel","family":"Trummer","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}]}],"member":"320","published-online":{"date-parts":[[2016,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2487754"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.91.042314"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCC.2006.876060"},{"key":"e_1_2_1_4_1","first-page":"278","volume-title":"Database and Expert Systems Applications","author":"Bellatreche L.","year":"2013","unstructured":"L. Bellatreche and S.-a. B. Senouci . SONIC : scalable multi-query optimization . In Database and Expert Systems Applications , pages 278 -- 292 . 2013 . L. Bellatreche and S.-a. B. Senouci. SONIC: scalable multi-query optimization. In Database and Expert Systems Applications, pages 278--292. 2013."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.111.130505"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms3067"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys2900"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-008-0082-9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-010-0200-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/170088.170181"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00031-X"},{"key":"e_1_2_1_12_1","volume-title":"A note on QUBO instances defined on Chimera graphs. arXiv preprint arXiv:1306.1202","author":"Dash S.","year":"2013","unstructured":"S. Dash . A note on QUBO instances defined on Chimera graphs. arXiv preprint arXiv:1306.1202 , 2013 . S. Dash. A note on QUBO instances defined on Chimera graphs. arXiv preprint arXiv:1306.1202, 2013."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.687980"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2015.01.026"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09465-6_6"},{"key":"e_1_2_1_16_1","volume-title":"Quantum computation by adiabatic evolution. arXiv preprint quant-ph\/0001106","author":"Farhi E.","year":"2000","unstructured":"E. Farhi , J. Goldstone , S. Gutmann , and M. Sipser . Quantum computation by adiabatic evolution. arXiv preprint quant-ph\/0001106 , 2000 . E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution. arXiv preprint quant-ph\/0001106, 2000."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.108.010501"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168654"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_20_1","volume-title":"Probing for quantum speedup in spin glass problems with planted solutions. arXiv preprint arXiv:1502.01663","author":"Hen I.","year":"2015","unstructured":"I. Hen , J. Job , J. Job , M. Troyer , and D. Lidar . Probing for quantum speedup in spin glass problems with planted solutions. arXiv preprint arXiv:1502.01663 , 2015 . I. Hen, J. Job, J. Job, M. Troyer, and D. Lidar. Probing for quantum speedup in spin glass problems with planted solutions. arXiv preprint arXiv:1502.01663, 2015."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-82375-6_11"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453864"},{"key":"e_1_2_1_23_1","volume-title":"Performance of a quantum annealer on range-limited constraint satisfaction problems. arXiv preprint arXiv:1502.02098","author":"King A. D.","year":"2015","unstructured":"A. D. King . Performance of a quantum annealer on range-limited constraint satisfaction problems. arXiv preprint arXiv:1502.02098 , 2015 . A. D. King. Performance of a quantum annealer on range-limited constraint satisfaction problems. arXiv preprint arXiv:1502.02098, 2015."},{"key":"e_1_2_1_24_1","volume-title":"Benchmarking a quantum annealing processor with the time-to-target metric. arXiv preprint arXiv:1508.05087","author":"King J.","year":"2015","unstructured":"J. King , S. Yarkoni , M. M. Nevisi , J. P. Hilton , and C. C. Mcgeoch . Benchmarking a quantum annealing processor with the time-to-target metric. arXiv preprint arXiv:1508.05087 , 2015 . J. King, S. Yarkoni, M. M. Nevisi, J. P. Hilton, and C. C. Mcgeoch. Benchmarking a quantum annealing processor with the time-to-target metric. arXiv preprint arXiv:1508.05087, 2015."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-013-0683-9"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.4.021041"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.37"},{"key":"e_1_2_1_28_1","volume-title":"Ising formulations of many NP problems. Frontiers in Physics, 2(5)","author":"Lucas A.","year":"2014","unstructured":"A. Lucas . Ising formulations of many NP problems. Frontiers in Physics, 2(5) , 2014 . A. Lucas. Ising formulations of many NP problems. Frontiers in Physics, 2(5), 2014."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2482767.2482797"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375703"},{"key":"e_1_2_1_31_1","volume-title":"Training a binary classifier with the quantium adiabatic algorithm. arXiv preprint arXiv:0811.0416","author":"Neven H.","year":"2008","unstructured":"H. Neven and V. Denchev . Training a binary classifier with the quantium adiabatic algorithm. arXiv preprint arXiv:0811.0416 , 2008 . H. Neven and V. Denchev. Training a binary classifier with the quantium adiabatic algorithm. arXiv preprint arXiv:0811.0416, 2008."},{"key":"e_1_2_1_32_1","volume-title":"Finding low-energy conformations of lattice protein models by quantum annealing. Scientific reports, 2","author":"Perdomo-Ortiz A.","year":"2012","unstructured":"A. Perdomo-Ortiz , N. Dickson , M. Drew-Brook , G. Rose , and A. Aspuru-Guzik . Finding low-energy conformations of lattice protein models by quantum annealing. Scientific reports, 2 , 2012 . A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik. Finding low-energy conformations of lattice protein models by quantum annealing. Scientific reports, 2, 2012."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjst\/e2015-02347-y"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1252319"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335419"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.54724"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/42201.42203"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(94)90014-0"},{"key":"e_1_2_1_39_1","volume-title":"a. Smolin, and U. Vazirani. How \"Quantum\" is the D-Wave Machine? arXiv preprint arXiv:1401.7087","author":"Shin S. W.","year":"2014","unstructured":"S. W. Shin , G. Smith , J. a. Smolin, and U. Vazirani. How \"Quantum\" is the D-Wave Machine? arXiv preprint arXiv:1401.7087 , 2014 . S. W. Shin, G. Smith, J. a. Smolin, and U. Vazirani. How \"Quantum\" is the D-Wave Machine? arXiv preprint arXiv:1401.7087, 2014."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_41_1","volume-title":"A near-term quantum computing approach for hard computational problems in space exploration. arXiv preprint arXiv:1204.2821","author":"Smelyanskiy V.","year":"2012","unstructured":"V. Smelyanskiy , E. G. Rieffel , S. I. Knysh , C. P. Williams , M. W. Johnson , M. C. Thom , W. G. Macready , and K. L. Pudenz . A near-term quantum computing approach for hard computational problems in space exploration. arXiv preprint arXiv:1204.2821 , 2012 . V. Smelyanskiy, E. G. Rieffel, S. I. Knysh, C. P. Williams, M. W. Johnson, M. C. Thom, W. G. Macready, and K. L. Pudenz. A near-term quantum computing approach for hard computational problems in space exploration. arXiv preprint arXiv:1204.2821, 2012."},{"key":"e_1_2_1_42_1","volume-title":"Classical signature of quantum annealing. arXiv preprint arXiv:1305.4904","author":"Smolin J.","year":"2013","unstructured":"J. Smolin and G. Smith . Classical signature of quantum annealing. arXiv preprint arXiv:1305.4904 , 2013 . J. Smolin and G. Smith. Classical signature of quantum annealing. arXiv preprint arXiv:1305.4904, 2013."},{"key":"e_1_2_1_43_1","volume-title":"Quantum optimization of fully-connected spin glasses. arXiv preprint arXiv:1406.7553","author":"Venturelli D.","year":"2014","unstructured":"D. Venturelli , S. Mandr\u00e0 , S. Knysh , B. O'Gorman , R. Biswas , and V. Smelyanskiy . Quantum optimization of fully-connected spin glasses. arXiv preprint arXiv:1406.7553 , 2014 . D. Venturelli, S. Mandr\u00e0, S. Knysh, B. O'Gorman, R. Biswas, and V. Smelyanskiy. Quantum optimization of fully-connected spin glasses. arXiv preprint arXiv:1406.7553, 2014."},{"key":"e_1_2_1_44_1","volume-title":"Quantum annealing implementation of job-shop scheduling. arXiv preprint arXiv:1506.08479","author":"Venturelli D.","year":"2015","unstructured":"D. Venturelli , D. J. J. Marchand , and G. Rojo . Quantum annealing implementation of job-shop scheduling. arXiv preprint arXiv:1506.08479 , 2015 . D. Venturelli, D. J. J. Marchand, and G. Rojo. Quantum annealing implementation of job-shop scheduling. arXiv preprint arXiv:1506.08479, 2015."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2947618.2947621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:33:11Z","timestamp":1672219991000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2947618.2947621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5]]},"references-count":44,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["10.14778\/2947618.2947621"],"URL":"https:\/\/doi.org\/10.14778\/2947618.2947621","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,5]]}}}