IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v604y2022ics0378437122005957.html
   My bibliography  Save this article

Quantum algorithms for anomaly detection using amplitude estimation

Author

Listed:
  • Guo, Mingchao
  • Liu, Hailing
  • Li, Yongmei
  • Li, Wenmin
  • Gao, Fei
  • Qin, Sujuan
  • Wen, Qiaoyan

Abstract

Anomaly detection, as an important branch of machine learning, plays a critical role in fraud detection, health care, intrusion detection, military surveillance, etc. An anomaly detection algorithm based on density estimation (called ADDE algorithm) is one of the widely used algorithms. However, the ADDE algorithm is computationally expensive when processing big data sets. To solve this problem, in this paper, we propose an efficient quantum ADDE algorithm based on amplitude estimation. It is shown that our algorithm achieves exponential speedup on the number of training data points M over its classical counterpart. Besides, the idea of our algorithm can be applied to accelerate the anomaly detection algorithm based on kernel principal component analysis (called ADKPCA algorithm), which also has a wide range of applications. Our algorithm shows exponential speedup on M compared with its classical counterpart.

Suggested Citation

  • Guo, Mingchao & Liu, Hailing & Li, Yongmei & Li, Wenmin & Gao, Fei & Qin, Sujuan & Wen, Qiaoyan, 2022. "Quantum algorithms for anomaly detection using amplitude estimation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 604(C).
    • Handle: RePEc:eee:phsmap:v:604:y:2022:i:c:s0378437122005957
    DOI: 10.1016/j.physa.2022.127936
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437122005957
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2022.127936?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jacob Biamonte & Peter Wittek & Nicola Pancotti & Patrick Rebentrost & Nathan Wiebe & Seth Lloyd, 2017. "Quantum machine learning," Nature, Nature, vol. 549(7671), pages 195-202, September.
    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. Ning, Tong & Yang, Youlong & Du, Zhenye, 2023. "Quantum kernel logistic regression based Newton method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 611(C).
    2. Wang, Sha-Sha & Liu, Hai-Ling & Song, Yan-Qi & Gao, Fei & Qin, Su-Juan & Wen, Qiao-Yan, 2023. "Quantum alternating operator ansatz for solving the minimum exact cover problem," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 626(C).
    3. Li, Jing & Gao, Fei & Lin, Song & Guo, Mingchao & Li, Yongmei & Liu, Hailing & Qin, Sujuan & Wen, QiaoYan, 2023. "Quantum k-fold cross-validation for nearest neighbor classification algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 611(C).
    4. Yu, Kai & Lin, Song & Guo, Gong-De, 2023. "Quantum dimensionality reduction by linear discriminant analysis," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 614(C).

    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. Wu, Jiang & Ou, Guiyan & Liu, Xiaohui & Dong, Ke, 2022. "How does academic education background affect top researchers’ performance? Evidence from the field of artificial intelligence," Journal of Informetrics, Elsevier, vol. 16(2).
    2. Li, Nianqiao & Yan, Fei & Hirota, Kaoru, 2022. "Quantum data visualization: A quantum computing framework for enhancing visual analysis of data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 599(C).
    3. Vicente Moret-Bonillo & Samuel Magaz-Romero & Eduardo Mosqueira-Rey, 2022. "Quantum Computing for Dealing with Inaccurate Knowledge Related to the Certainty Factors Model," Mathematics, MDPI, vol. 10(2), pages 1-21, January.
    4. Gong, Li-Hua & Xiang, Ling-Zhi & Liu, Si-Hang & Zhou, Nan-Run, 2022. "Born machine model based on matrix product state quantum circuit," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 593(C).
    5. Laura Böhm & Sebastian Kolb & Thomas Plankenbühler & Jonas Miederer & Simon Markthaler & Jürgen Karl, 2023. "Short-Term Natural Gas and Carbon Price Forecasting Using Artificial Neural Networks," Energies, MDPI, vol. 16(18), pages 1-25, September.
    6. Alen Senanian & Sridhar Prabhu & Vladimir Kremenetski & Saswata Roy & Yingkang Cao & Jeremy Kline & Tatsuhiro Onodera & Logan G. Wright & Xiaodi Wu & Valla Fatemi & Peter L. McMahon, 2024. "Microwave signal processing using an analog quantum reservoir computer," Nature Communications, Nature, vol. 15(1), pages 1-9, December.
    7. Jonas Jäger & Roman V. Krems, 2023. "Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines," Nature Communications, Nature, vol. 14(1), pages 1-7, December.
    8. Olawale Ayoade & Pablo Rivas & Javier Orduz, 2022. "Artificial Intelligence Computing at the Quantum Level," Data, MDPI, vol. 7(3), pages 1-16, February.
    9. Wei-Ming Li & Shi-Ju Ran, 2022. "Non-Parametric Semi-Supervised Learning in Many-Body Hilbert Space with Rescaled Logarithmic Fidelity," Mathematics, MDPI, vol. 10(6), pages 1-15, March.
    10. Johannes Herrmann & Sergi Masot Llima & Ants Remm & Petr Zapletal & Nathan A. McMahon & Colin Scarato & François Swiadek & Christian Kraglund Andersen & Christoph Hellings & Sebastian Krinner & Nathan, 2022. "Realizing quantum convolutional neural networks on a superconducting quantum processor to recognize quantum phases," Nature Communications, Nature, vol. 13(1), pages 1-7, December.
    11. Matthias C. Caro & Hsin-Yuan Huang & Nicholas Ezzell & Joe Gibbs & Andrew T. Sornborger & Lukasz Cincio & Patrick J. Coles & Zoë Holmes, 2023. "Out-of-distribution generalization for learning quantum dynamics," Nature Communications, Nature, vol. 14(1), pages 1-9, December.
    12. Naughtin, Claire & Hajkowicz, Stefan & Schleiger, Emma & Bratanova, Alexandra & Cameron, Alicia & Zamin, T & Dutta, A, 2022. "Our Future World: Global megatrends impacting the way we live over coming decades," MPRA Paper 113900, University Library of Munich, Germany.
    13. Jing, Hang & Li, Yan & Brandsema, Matthew J. & Chen, Yousu & Yue, Meng, 2024. "HHL algorithm with mapping function and enhanced sampling for model predictive control in microgrids," Applied Energy, Elsevier, vol. 361(C).
    14. Liu, Hai-Ling & Yu, Chao-Hua & Wan, Lin-Chun & Qin, Su-Juan & Gao, Fei & Wen, Qiaoyan, 2022. "Quantum mean centering for block-encoding-based quantum algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 607(C).
    15. Ajagekar, Akshay & You, Fengqi, 2022. "Quantum computing and quantum artificial intelligence for renewable and sustainable energy: A emerging prospect towards climate neutrality," Renewable and Sustainable Energy Reviews, Elsevier, vol. 165(C).
    16. Michael Ragone & Bojko N. Bakalov & Frédéric Sauvage & Alexander F. Kemper & Carlos Ortiz Marrero & Martín Larocca & M. Cerezo, 2024. "A Lie algebraic theory of barren plateaus for deep parameterized quantum circuits," Nature Communications, Nature, vol. 15(1), pages 1-10, December.
    17. Daniel J. Egger & Claudio Gambella & Jakub Marecek & Scott McFaddin & Martin Mevissen & Rudy Raymond & Andrea Simonetto & Stefan Woerner & Elena Yndurain, 2020. "Quantum Computing for Finance: State of the Art and Future Prospects," Papers 2006.14510, arXiv.org, revised Jan 2021.
    18. Lei, Jiancheng & Song, Tingting & Liu, Ling & Zhang, Kejia, 2023. "An improved quantum algorithm for data fitting," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 613(C).
    19. Sofiene Jerbi & Casper Gyurik & Simon C. Marshall & Riccardo Molteni & Vedran Dunjko, 2024. "Shadows of quantum machine learning," Nature Communications, Nature, vol. 15(1), pages 1-7, December.
    20. Yuqian Zhao & Zhaohua Ma & Zhangzhen He & Haijun Liao & Yan-Cheng Wang & Junfeng Wang & Yuesheng Li, 2024. "Quantum annealing of a frustrated magnet," Nature Communications, Nature, vol. 15(1), pages 1-9, December.

    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:eee:phsmap:v:604:y:2022:i:c:s0378437122005957. 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: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.