Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Quantum Information Processing
Published in: Quantum Information Processing 1/2019

01-01-2019

Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network scheduling

Authors: Chi Wang, Edmond Jonckheere

Published in: Quantum Information Processing | Issue 1/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

With the introduction of adiabatic quantum computation (AQC) and its implementation on D-Wave annealers, there has been a constant quest for benchmark problems that would allow for a fair comparison between such classical combinatorial optimization techniques as simulated annealing (SA) and AQC-based optimization. Such a benchmark case study has been the scheduling problem to avoid interference in the very specific Dirichlet protocol in wireless networking, where it was shown that the gap expansion to retain noninterference solutions benefits AQC better than SA. Here, we show that the same gap expansion allows for significant improvement in the D-Wave 2X solution compared with that of its predecessor, the D-Wave II.
next article Quantum Penny Flip game with unawareness

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
2.
3.
4.
Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, pp. 212–219 (1996)
5.
6.
7.
Boixo, S., Rnnow, T.F., Isakov, S.V., Wang, Z., Wecker, D., Lidar, D.A., Martinis, J.M., Troyer, M.: Evidence of quantum annealing with more than one hundred qubits. Nat. Phys. 10(3), 218–224 (2014)CrossRef
8.
Rnnow, T.F., Wang, Z., Job, J., Boixo, S., Isakov, S.V., Wecker, D., Martinis, J.M., Lidar, D.A., Troyer, M.: Defining and detecting quantum speedup. Science 345(6195), 420–424 (2014)CrossRefADS
9.
Lanting, T.: Entanglement in a quantum annealing processor. Phys. Rev. X 4, 021041 (2014)
10.
Boixo, S., et al.: Computational multiqubit tunnelling in programmable quantum annealers. Nat. Commun. 7, 10327 (2016)CrossRefADS
11.
Hen, I., Job, J., Albash, T., Rnnow, T.F., Troyer, M., Lidar, D.A.: Probing for quantum speedup in spin glass problems with planted solutions. Phys. Rev. A 92(4), 042325 (2015)CrossRefADS
12.
Katzgraber, H., Hamze, F., Andrist, R.: Glassy chimeras could be blind to quantum speedup: designing better benchmarks for quantum annealing machines. Phys. Rev. X 4, 021008 (2014)
13.
14.
Denchev, V., et al.: What is the computational value of finite range tunneling. Phys. Rev. X 6, 031015 (2016)
15.
Childs, A.M., Maslov, D., Nam, Y., Ross, N.J., Su, Y.: Towards the first quantum simulation with quantum speedup. arXiv:​1711.​10980v1 [quant-ph] 29 Nov 2017]
16.
Pudenz, K., Albash, T., Lidar, D.A.: Error corrected quantum annealing with hundreds of qubits. Nat. Commun. 5, 3243 (2014)CrossRefADS
17.
18.
19.
20.
Perdomo-Ortiz, A., Benedetti, M., Realpe-Gomez, J., Biswas, R.: Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers. arXiv:​1708.​09757v2 [quant-ph] 19 Mar (2018)
21.
Banirazi, R., Jonckheere, E., Krishnamachari, B.: Heat diffusion algorithm for resource allocation and routing in multihop wireless networks. In: GLOBECOM, Anaheim, California, USA, pp. 5915–5920 (2012)
22.
Banirazi, R., Jonckheere, E., Krishnamachari, B.: Dirichlet’s principle on multiclass multihop wireless networks: minimum cost routing subject to stability. Analysis and Simulation of Wireless and Mobile Systems, Montreal, Canada, pp. 31–40 (2014)
23.
Banirazi, R., Jonckheere, E., Krishnamachari, B.: Heat diffusion optimal dynamic routing for multiclass multihop wireless networks. In: INFOCOM, Toronto, Canada, pp. 325–333 (2014)
24.
Ghosh, P., Ren, He, Banirazi, R., Krishnamachari, B., Jonckheere, E.: Empirical evaluation of the heat-diffusion collection protocol for wireless sensor networks. Comput. Netw. (COMNET) 127, 217–232 (2017)CrossRef
25.
Banirazi, R., Jonckheere, E., Krishnamachari, B., Minimum delay in class of throughput-optimal control policies on wireless networks. In: American Control Conference (ACC), Portland, OR, pp. 2668–2675 (2014)
26.
Tassiulas, L., Ephremides, A.: Stability properties of constrained queueing systems and scheduling policies for maximal throughput in multihop radio networks. IEEE Trans. Autom. Control 37(12), 1936–1948 (1992)CrossRefMATH
27.
Wang, C., Chen, H., Jonckheere, E.: Quantum versus simulated annealing in wireless interference network optimization. Sci. Rep. 6, 25797 (2016)CrossRefADS
28.
Jonckheere, E.A., Rezakhani, A.T., Ahmad, F.: Differential topology of adiabatically controlled quantum processes. Quantum Inf. Process. 12(3), 1515–1538 (2013). Special Issue on Quantum ControlCrossRefADSMathSciNetMATH
29.
Jonckheere, E.A., Ahmad, F., Gutkin, E.: Differential topology of numerical range. Linear Algebra Appl. 279(1–3), 227–254 (1998)CrossRefMathSciNetMATH
30.
Wang, C., Jonckheere, E., Brun, T.: Ollivier–Ricci curvature and fast approximation to tree-width in embeddability of QUBO problems. In: ISCCSP, Athens, Greece, pp. 639–642 (2014)
31.
Wang, C., Jonckheere, E., Brun, T.: Differential geometric treewidth estimation in adiabatic quantum computation. Quantum Inf. Process. 15(10), 3951–3966 (2016)CrossRefADSMathSciNetMATH
32.
Wang, C., Jonckheere, E., Banirazi, R.: Wireless network capacity versus Ollivier–Ricci curvature under heat diffusion (HD) protocol. In: American Control Conference (ACC 2014), Portland, OR, pp. 3536–3541 (2014)
33.
Wang, C., Jonckheere, E., Banirazi, R.: Interference constrained network performance control based on curvature control. In: 2016 American Control Conference, Boston, USA, pp. 6036–6041 (2016)
34.
Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E.: A survey on sensor network. IEEE Commun. Mag. 40(8), 102–114 (2002)CrossRef
35.
Karp, B., Kung, H.T.: GPSR: Greedy perimeter stateless routing for wireless networks. In: Proceedings ACM MobiCom’00, Boston, MA, pp. 243–254 (2000)
36.
37.
Bianchi, G.: Performance analysis of the IEEE 802.11 distributed coordination function. IEEE J. Sel. Areas Commun. 18, 535–547 (2000)CrossRef
38.
Cali, F.: Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit. IEEE/ACM Trans. Netw. 8, 785–799 (2000)CrossRef
39.
Jain, K., Padhey, J., Padmanabhan, V.N., Qiu, L.: Impact of interference on multi-hop wireless network performance. In: MobiCom ’03, San Diego, California, USA, pp. 66–80 (2003)
40.
Alicherry, A., Bhatia, R., Li, L.E.: Joint channel assignment and routing for throughput optimization in multiradio wireless mesh networks. IEEE J. Sel. Areas Commun. 24(11), 1960–1971 (2006)CrossRef
41.
Kodialam, M., Nandagopal, T.: Characterizing the capacity region in multi-radio multi-channel wireless mesh networks. In: MobiCom’05, ACM, Cologne, Germany, pp. 73–87 (2005)
42.
Sanghavi, S.S., Bui, L., Srikant, R.: Distributed link scheduling with constant overhead. ACM SIGMETRICS 35(1), 313–324 (2007)CrossRef
43.
Wan, P.J.: Multiflows in multihop wireless networks. In: MobiHoc’09, New Orleans, LA, USA, pp. 85–94 (2009)
44.
Blough, D.M., Resta, G., Sant, P.: Approximation algorithms for wireless link scheduling with SINR-based interference. IEEE Trans. Netw. 18(6), 1701–1712 (2010)CrossRef
45.
Chafekar, D., Anil Kumar, V.S., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: Capacity of wireless networks under SINR interference constraints. Wirel. Netw. 17, 1605–1624 (2011)CrossRef
46.
Moscibroda, T., Wattenhofer, R., Zollinger, A.: Topology control meets SINR: the scheduling complexity of arbitrary topologies. In: MobiHoc’06, ACM, Florence, Italy, pp. 310–321 (2006)
47.
48.
Andrews, M., Dinitz, M.: Maximizing capacity in arbitrary wireless networks in the SINR model: complexity and game theory. In: INFOCOM’09, Rio de Janeiro, pp. 1332–1340 (2009)
49.
Sharma, G., Mazumdar, R., Shroff, N.: On the complexity of scheduling in wireless networks. In: MobiCom’06, Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, Los Angeles, CA, pp. 227–238 (2006)
50.
51.
Dimakis, A., Walrand, J.: Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits. Adv. Appl. Probab. 38(2), 505–521 (2006)CrossRefMathSciNetMATH
52.
Joo, C., Lin, X., Shroff, N.: Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks. IEEE/ACM Trans. Netw. 17(4), 1132–1145 (2009)CrossRef
53.
Zussman, G., Brzezinski, A., Modiano, E.: Multihop local pooling for distributed throughput maximization in wireless networks. In: INFOCOM’08, Phoenix, Arizona (2008)
54.
Leconte, M., Ni, J., Srikant, R.: Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks. In: MOBIHOC’09, pp. 165–174 (2009)
55.
Li, B., Boyaci, C., Xia, Y.: A refined performance characterization of longest-queue-first policy in wireless networks. In: ACM MOBIHOC, New York, NY, USA, pp. 65–74 (2009)
56.
Brzezinski, A., Zussman, G., Modiano, E.: Distributed throughput maximization in wireless mesh networks via pre-partitioning. IEEE/ACM Trans. Netw. 16(6), 1406–1419 (2008)CrossRef
57.
Proutiere, A., Yi Y., Chiang, M.: Throughput of random access without message passing. In: 42nd Annual Conference on Information Sciences and Systems, Princeton, NJ, USA, pp. 509–514 (2008)
58.
Jonckheere, E., Lou, M., Bonahon, F., Baryshnikov, Y.: Euclidean versus hyperbolic congestion in idealized versus experimental networks. Internet Math. 7(1), 1–27 (2011)CrossRefMathSciNetMATH
59.
Homer, S., Peinado, M.: Experiments with polynomial-time clique approximation algorithms on very large graphs. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS Series. American Mathematical Society, Providence, RI (1996)
60.
Xu, X., Ma, J., An, H.W.: Improved simulated annealing algorithm for the maximum independent set problem. Intelligent Computing, Volume 4113 of the series Lecture Notes in Computer Science, pp. 822–831 (2006)
61.
Kim, Y.G., Lee, M.G.: Scheduling multi-channel and multi-timeslot in time constrained wireless sensor networks via simulated annealing and particle swarm optimization. IEEE Commun. Mag. 52(1), 122–129 (2014)CrossRef
62.
Mappar, M., Rahmani, A.M., Ashtari, A.H.: A new approach for sensor scheduling in wireless sensor networks using simulated annealing. In: ICCIT ’09. Fourth International Conference on Computer Sciences and Convergence Information Technology, Seoul, Korea, pp. 746–750 (2009)
63.
Grossman, T.: Applying the INN model to the max clique problem. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS Series. American Mathematical Society, Providence, RI (1996)
64.
Jagota, A.: Approximating maximum clique with a Hopfield network. IEEE Trans. Neural Netw. 6, 724–735 (1995)CrossRef
65.
Jagota, A., Sanchis, L., Ganesan, R.: Approximately solving maximum clique using neural networks and related heuristics. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS Series. American Mathematical Society, Providence, RI (1996)
66.
Bui, T.N., Eppley, P.H.: A hybrid genetic algorithm for the maximum clique problem. In: Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, PA, pp. 478–484 (1995)
67.
Hifi, M.: A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems. J. Oper. Res. Soc. 48, 612–622 (1997)CrossRefMATH
68.
Marchiori, E.: Genetic, iterated and multistart local search for the maximum clique problem. Applications of Evolutionary Computing. volume 2279 of Lecture Notes in Computer Science, pp. 112–121. Springer, Berlin (2002)
69.
Feo, T.A., Resende, M.: A greedy randomized adaptive search procedure for maximum independent set. Oper. Res. 42, 860–878 (1994)CrossRefMATH
70.
71.
Friden, C., Hertz, A., de Werra, D.: Stabulus: a technique for finding stable sets in large graphs with tabu search. Computing 42, 35–44 (1989)CrossRefMATH
72.
Mannino, C., Stefanutti, E.: An augmentation algorithm for the maximum weighted stable set problem. Comput. Optim. Appl. 14, 367–381 (1999)CrossRefMathSciNetMATH
73.
Soriano, P., Gendreau, M.: Tabu search algorithms for the maximum clique problem. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS Series. American Mathematical Society, Providence, RI (1996)
74.
Reichardt, B.W.: The quantum adiabatic optimization algorithm and local minima. In: STOC ’04, Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, Chicago, IL, pp. 502–510 (2004)
75.
Felzenszwalb, P.F.: Dynamic programming and graph algorithms in computer vision. IEEE Trans. Pattern Anal. Mach. Intell. 33(4), 721–740 (2011)CrossRef
76.
Trummer, I., Koch, C.: Multiple query optimization on the D-Wave 2X adiabatic quantum computer. Proc. VLDB Endow. 9(9), 648–659 (2016)CrossRef
77.
O’Gorman, B., Babbush, R., Perdomo-Ortiz, A., Aspuru-Guzik, A., Smelyanskiy, V.: Bayesian network structure learning using quantum annealing. Eur. Phys. J. Spec. Top. 224(1), 163–188 (2015)CrossRef
78.
Rieffel, E.G., Venturelli, D., O’Gorman, B., Do, M.B., Prystay, E., Smelyanskiy, V.N.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14(1), 1–36 (2015)CrossRefADSMATH
79.
Perdomo-Ortiz, A., Fluegemann, J., Narasimhan, S., Biswas, R., Smelyanskiy, V.N.: A quantum annealing approach for fault detection and diagnosis of graph-based systems. Eur. Phys. J. Spec. Top. 224(1), 131–148 (2015)CrossRef
80.
81.
Benedetti, M., Realpe-Gmez, J., Biswas, R., Perdomo-Ortiz, A.: Estimation of effective temperatures in a quantum annealer and its impact in sampling applications: a case study towards deep learning applications. Phys. Rev. A 94(2), 022308 (2016)CrossRefADS
82.
Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193–209 (2008)CrossRefMathSciNetMATH
83.
Bian, Z., Chudak, F., Macready, W.G., Clark, L., Gaitan, F.: Experimental determination of Ramsey numbers. Phys. Rev. Lett. 111, 130505 (2013)CrossRefADS
84.
Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10(3), 343–353 (2011)CrossRefMathSciNetMATH
85.
Vinci, W., et al.: Quantum annealing correction with minor embedding. Phys. Rev. A 92, 042310 (2015)CrossRefADS
86.
Vinci, W., Albash, T., Lidar, D.A.: Nested quantum annealing correction. npj Quantum Inf. 2, 16017 (2016)CrossRefADS
87.
Mishra, A., Albash, T., Lidar, D.A.: Performance of two different quantum annealing correction codes. Quantum Inf. Process. 15(2), 609–636 (2016)CrossRefADSMathSciNetMATH
88.
Isakov, S.V., Zintchenko, I.N., Rnnow, T.F., Troyer, M.: Optimized simulated annealing for Ising spin glasses. Comput. Phys. Commun. 192, 265–271 (2015)CrossRefADSMathSciNetMATH
89.
90.
Bauer, F., Jost, J., Liu, S.: Ollivier–Ricci curvature and the spectrum of the normalized graph Laplace operator. Math. Res. Lett. 19(6), 1185–1205 (2012)CrossRefMathSciNetMATH
Metadata
Title
Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network scheduling
Authors
Chi Wang
Edmond Jonckheere
Publication date
01-01-2019
Publisher
Springer US
Published in
Quantum Information Processing / Issue 1/2019
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-018-2117-1

Other articles of this Issue 1/2019

Quantum Information Processing 1/2019 Go to the issue

OriginalPaper

Real-time selection for free-space measurement device independent quantum key distribution

OriginalPaper

Triangle-like inequalities related to coherence and entanglement negativity

OriginalPaper

Polygamy relation for the Rényi- entanglement of assistance in multi-qubit systems

OriginalPaper

Non-Gaussian swapping of entangled resources

OriginalPaper

Any quantum network is structurally controllable by a single driving signal

OriginalPaper

One-step implementation of a multiqubit controlled-phase-flip gate in coupled cavities