On the Super-exponential Quantum Speedup of Equivariant Quantum Machine Learning Algorithms with SU($d$) Symmetry

• URL: http://arxiv.org/abs/2207.07250v1
• Date: Fri, 15 Jul 2022 01:41:53 GMT
• Title: On the Super-exponential Quantum Speedup of Equivariant Quantum Machine Learning Algorithms with SU($d$) Symmetry
• Authors: Han Zheng, Zimu Li, Junyu Liu, Sergii Strelchuk, Risi Kondor
• Abstract summary: We enhance a natural model of quantum computation--permutational quantum computing (PQC)--and defines a more powerful model: PQC+. While PQC was shown to be effectively classically simulatable, we exhibit a problem which can be efficiently solved on PQC+ machine. We discuss practical quantum machine learning algorithms which can be carried out in the paradigm of PQC+.
• Score: 14.281289319738633
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a framework of the equivariant convolutional algorithms which is tailored for a number of machine-learning tasks on physical systems with arbitrary SU($d$) symmetries. It allows us to enhance a natural model of quantum computation--permutational quantum computing (PQC) [Quantum Inf. Comput., 10, 470-497 (2010)] --and defines a more powerful model: PQC+. While PQC was shown to be effectively classically simulatable, we exhibit a problem which can be efficiently solved on PQC+ machine, whereas the best known classical algorithms runs in $O(n!n^2)$ time, thus providing strong evidence against PQC+ being classically simulatable. We further discuss practical quantum machine learning algorithms which can be carried out in the paradigm of PQC+.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• The Power of Lorentz Quantum Computer [6.9754404995027794]
  We demonstrate the superior capabilities of the recently proposed Lorentz quantum computer (LQC) compared to conventional quantum computers. We introduce an associated computational complexity class $text Psharp textP$, demonstrating its equivalence to the complexity class $text Psharp textP$. We show that the quantum computing with postselection proposed by Aaronson can be efficiently simulated by LQC, but not vice versa.
  arXiv  Detail & Related papers  (2024-03-07T03:00:09Z)
• QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
  We focus on variational quantum circuits (VQC), which emerged as the most promising candidates for the quantum counterpart of neural networks. Although showing promising results, VQCs can be hard to train because of different issues, e.g., barren plateau, periodicity of the weights, or choice of architecture. We propose a gradient-free algorithm inspired by natural evolution to optimize both the weights and the architecture of the VQC.
  arXiv  Detail & Related papers  (2023-04-14T08:03:20Z)
• Quantum computing quantum Monte Carlo with hybrid tensor network for electronic structure calculations [3.642843803494657]
  We propose an algorithm combining QC-QMC with a hybrid tensor network to extend the applicability of QC-QMC beyond a single quantum device size. Our algorithm is evaluated on the Heisenberg chain model, graphite-based Hubbard model, hydrogen plane model, and MonoArylBiImidazole using full configuration interaction QMC.
  arXiv  Detail & Related papers  (2023-03-31T14:38:40Z)
• TeD-Q: a tensor network enhanced distributed hybrid quantum machine learning framework [59.07246314484875]
  TeD-Q is an open-source software framework for quantum machine learning. It seamlessly integrates classical machine learning libraries with quantum simulators. It provides a graphical mode in which the quantum circuit and the training progress can be visualized in real-time.
  arXiv  Detail & Related papers  (2023-01-13T09:35:05Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Machine Learning for Software Supply Chain Attacks: How Far Can We Go? [5.655023007686363]
  This paper analyzes speed up performance of QC when applied to machine learning algorithms, known as Quantum Machine Learning (QML) Due to limitations of real quantum computers, the QML methods were implemented on open-source quantum simulators such as Qiskit and IBM Quantum. Interestingly, the experimental results differ to the speed up promises of QC by demonstrating higher computational time and lower accuracy in comparison to the classical approaches for SSC attacks.
  arXiv  Detail & Related papers  (2022-04-04T21:16:06Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Fast-Forwarding with NISQ Processors without Feedback Loop [0.0]
  We present the Classical Quantum Fast Forwarding (CQFF) as an alternative diagonalisation based algorithm for quantum simulation. CQFF removes the need for a classical-quantum feedback loop and controlled multi-qubit unitaries. Our work provides a $104$ improvement over the previous record.
  arXiv  Detail & Related papers  (2021-04-05T14:29:33Z)
• NISQ Algorithm for Hamiltonian Simulation via Truncated Taylor Series [0.0]
  Noisy intermediate-scale quantum (NISQ) algorithms aim at effectively using the currently available quantum hardware. We propose a new algorithm, truncated Taylor quantum simulator (TTQS), that shares the advantages of existing algorithms and alleviates some of the shortcomings. Our algorithm does not have any classical-quantum feedback loop and bypasses the barren plateau problem by construction.
  arXiv  Detail & Related papers  (2021-03-09T15:48:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.