The Power of Lorentz Quantum Computer

• URL: http://arxiv.org/abs/2403.04170v2
• Date: Mon, 2 Sep 2024 08:18:30 GMT
• Title: The Power of Lorentz Quantum Computer
• Authors: Qi Zhang, Biao Wu,
• Abstract summary: 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.
• Score: 6.9754404995027794
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 termed bounded-error Lorentz quantum polynomial-time (BLQP), demonstrating its equivalence to the complexity class ${\text P}^{\sharp \text{P}}$. We present LQC algorithms that efficiently solve the problem of maximum independent set, PP (probabilistic polynomial-time), and consequently ${\text P}^{\sharp \text{P}}$, all within polynomial time. Additionally, we show that the quantum computing with postselection proposed by Aaronson can be efficiently simulated by LQC, but not vice versa.

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)
• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians [0.0]
  We show that non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. We also show that there exists (quantum) oracles relative to which certain quantum PCP statements are false.
  arXiv  Detail & Related papers  (2024-03-07T19:00:06Z)
• Demystifying Quantum Power Flow: Unveiling the Limits of Practical Quantum Advantage [2.8498944632323755]
  Quantum computers hold promise for solving problems intractable for classical computers. The speedup due to quantum power flow algorithms is claimed to be exponential when compared to classical PF solved by state-of-the-art algorithms. We investigate the potential for practical quantum advantage (PQA) in solving QPF compared to classical methods on gate-based quantum computers.
  arXiv  Detail & Related papers  (2024-02-13T17:36:18Z)
• 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 Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Optimal Stochastic Resource Allocation for Distributed Quantum Computing [50.809738453571015]
  We propose a resource allocation scheme for distributed quantum computing (DQC) based on programming to minimize the total deployment cost for quantum resources. The evaluation demonstrates the effectiveness and ability of the proposed scheme to balance the utilization of quantum computers and on-demand quantum computers.
  arXiv  Detail & Related papers  (2022-09-16T02:37:32Z)
• On the Super-exponential Quantum Speedup of Equivariant Quantum Machine Learning Algorithms with SU($d$) Symmetry [14.281289319738633]
  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+.
  arXiv  Detail & Related papers  (2022-07-15T01:41:53Z)
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection [0.0]
  We show that any problem in $sf PostBQP$ can be solved with only postselections whose probabilities are close to one. We also show that a single rewind operator is sufficient to achieve tasks that are intractable for quantum computation.
  arXiv  Detail & Related papers  (2022-06-11T06:19:24Z)
• 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)
• Quantum Logarithmic Space and Post-selection [0.4588028371034406]
  Post-selection is an influential concept introduced to the field of quantum complexity theory by Aaronson (Proceedings of the Royal Society A, 2005) Our main result shows the identity $sf PostBQL=$, i.e., the class of problems that can be solved by a bounded-error (polynomial-time) logarithmic-space quantum algorithm with post-selection ($sf PostBQL$) We also show that $sf$ coincides with the class of problems that can be solved by bounded-error logarithmic-space quantum algorithms that have no time bound.
  arXiv  Detail & Related papers  (2021-05-06T14:02:01Z)

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.