IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0206653.html
   My bibliography  Save this article

Nonnegative/Binary matrix factorization with a D-Wave quantum annealer

Author

Listed:
  • Daniel O’Malley
  • Velimir V Vesselinov
  • Boian S Alexandrov
  • Ludmil B Alexandrov

Abstract

D-Wave quantum annealers represent a novel computational architecture and have attracted significant interest. Much of this interest has focused on the quantum behavior of D-Wave machines, and there have been few practical algorithms that use the D-Wave. Machine learning has been identified as an area where quantum annealing may be useful. Here, we show that the D-Wave 2X can be effectively used as part of an unsupervised machine learning method. This method takes a matrix as input and produces two low-rank matrices as output—one containing latent features in the data and another matrix describing how the features can be combined to approximately reproduce the input matrix. Despite the limited number of bits in the D-Wave hardware, this method is capable of handling a large input matrix. The D-Wave only limits the rank of the two output matrices. We apply this method to learn the features from a set of facial images and compare the performance of the D-Wave to two classical tools. This method is able to learn facial features and accurately reproduce the set of facial images. The performance of the D-Wave shows some promise, but has some limitations. It outperforms the two classical codes in a benchmark when only a short amount of computational time is allowed (200-20,000 microseconds), but these results suggest heuristics that would likely outperform the D-Wave in this benchmark.

Suggested Citation

  • Daniel O’Malley & Velimir V Vesselinov & Boian S Alexandrov & Ludmil B Alexandrov, 2018. "Nonnegative/Binary matrix factorization with a D-Wave quantum annealer," PLOS ONE, Public Library of Science, vol. 13(12), pages 1-12, December.
    • Handle: RePEc:plo:pone00:0206653
    DOI: 10.1371/journal.pone.0206653
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0206653
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0206653&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0206653?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Daniel D. Lee & H. Sebastian Seung, 1999. "Learning the parts of objects by non-negative matrix factorization," Nature, Nature, vol. 401(6755), pages 788-791, October.
    2. Fred Glover, 1990. "Tabu Search—Part II," INFORMS Journal on Computing, INFORMS, vol. 2(1), pages 4-32, February.
    3. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    4. Elizabeth Gibney, 2017. "D-Wave upgrade: How scientists are using the world’s most controversial quantum computer," Nature, Nature, vol. 541(7638), pages 447-448, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fred Glover & Gary Kochenberger & Rick Hennig & Yu Du, 2022. "Quantum bridge analytics I: a tutorial on formulating and using QUBO models," Annals of Operations Research, Springer, vol. 314(1), pages 141-183, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mohammad Javad Feizollahi & Igor Averbakh, 2014. "The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 321-335, May.
    2. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    3. Cazzaro, Davide & Fischetti, Martina & Fischetti, Matteo, 2020. "Heuristic algorithms for the Wind Farm Cable Routing problem," Applied Energy, Elsevier, vol. 278(C).
    4. Huang, Yeran & Yang, Lixing & Tang, Tao & Gao, Ziyou & Cao, Fang, 2017. "Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks," Energy, Elsevier, vol. 138(C), pages 1124-1147.
    5. B Dengiz & C Alabas-Uslu & O Dengiz, 2009. "Optimization of manufacturing systems using a neural network metamodel with a new training approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1191-1197, September.
    6. S-W Lin & K-C Ying, 2008. "A hybrid approach for single-machine tardiness problems with sequence-dependent setup times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1109-1119, August.
    7. Joseph B. Mazzola & Robert H. Schantz, 1997. "Multiple‐facility loading under capacity‐based economies of scope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(3), pages 229-256, April.
    8. Abdmouleh, Zeineb & Gastli, Adel & Ben-Brahim, Lazhar & Haouari, Mohamed & Al-Emadi, Nasser Ahmed, 2017. "Review of optimization techniques applied for the integration of distributed generation from renewable energy sources," Renewable Energy, Elsevier, vol. 113(C), pages 266-280.
    9. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.
    10. Chris S. K. Leung & Henry Y. K. Lau, 2018. "Multiobjective Simulation-Based Optimization Based on Artificial Immune Systems for a Distribution Center," Journal of Optimization, Hindawi, vol. 2018, pages 1-15, May.
    11. Ilfat Ghamlouche & Teodor Gabriel Crainic & Michel Gendreau, 2003. "Cycle-Based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design," Operations Research, INFORMS, vol. 51(4), pages 655-667, August.
    12. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    13. Andaryan, Abdullah Zareh & Mousighichi, Kasra & Ghaffarinasab, Nader, 2024. "A heuristic approach to the stochastic capacitated single allocation hub location problem with Bernoulli demands," European Journal of Operational Research, Elsevier, vol. 312(3), pages 954-968.
    14. Panta Lučić & Dušan Teodorović, 2007. "Metaheuristics approach to the aircrew rostering problem," Annals of Operations Research, Springer, vol. 155(1), pages 311-338, November.
    15. Haluk Yapicioglu, 2018. "Multiperiod Multi Traveling Salesmen Problem Considering Time Window Constraints with an Application to a Real World Case," Networks and Spatial Economics, Springer, vol. 18(4), pages 773-801, December.
    16. Marco Antonio Boschetti & Vittorio Maniezzo, 2022. "Matheuristics: using mathematics for heuristic design," 4OR, Springer, vol. 20(2), pages 173-208, June.
    17. C-H Lan & C-C Chen, 2007. "Optimal purchase of two-itemized drugs for a disease," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 309-316, March.
    18. G Lulli & U Pietropaoli & N Ricciardi, 2011. "Service network design for freight railway transportation: the Italian case," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(12), pages 2107-2119, December.
    19. Cheung, Kam-Fung & Bell, Michael G.H., 2021. "Improving connectivity of compromised digital networks via algebraic connectivity maximisation," European Journal of Operational Research, Elsevier, vol. 294(1), pages 353-364.
    20. Dimitris Fouskakis & David Draper, 2002. "Stochastic Optimization: a Review," International Statistical Review, International Statistical Institute, vol. 70(3), pages 315-349, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0206653. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.