The Power of Lorentz Quantum Computer
- URL: http://arxiv.org/abs/2403.04170v1
- Date: Thu, 7 Mar 2024 03:00:09 GMT
- Title: The Power of Lorentz Quantum Computer
- Authors: Qi Zhang and Biao Wu
- Abstract summary: We demonstrate the superior capabilities of the recently proposed Lorentz quantum computer (LQC) compared to conventional quantum computers.
We present LQC algorithms that solve in time the problem of maximum independent set and the problems in the classes of NP, co-NP, PH (polynomial hierarchy), PP (probabilistic-time), and $text Psharp textP$.
- Score: 8.240558902431976
- 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, bounded-error Lorentz quantum
polynomial-time (BLQP), and prove that the complexity class ${\text P}^{\sharp
\text{P}}$ is contained within BLQP. We present LQC algorithms that solve in
polynomial time the problem of maximum independent set and the problems in the
classes of NP, co-NP, PH (polynomial hierarchy), PP (probabilistic
polynomial-time), and ${\text P}^{\sharp \text{P}}$. We show that the quantum
computing with postselection proposed by Aaronson can be simulated efficiently
by LQC, but not vice versa.
Related papers
- 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) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$.
In particular, we design global protocols for small set expansion, unique games, and PCP verification.
We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
arXiv Detail & Related papers (2024-02-29T01:35:46Z) - 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 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) - Universal expressiveness of variational quantum classifiers and quantum
kernels for support vector machines [0.0]
We show that variational quantum classifiers (VQC) and support vector machines with quantum kernels (QSVM) can solve a classification problem based on the k-Forrelation problem.
Our results imply that there exists a feature map and a quantum kernel that make VQC and QSVM efficient solvers for any BQP problem.
arXiv Detail & Related papers (2022-07-12T22:03:31Z) - 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 communication complexity beyond Bell nonlocality [87.70068711362255]
Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks.
Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts.
We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
arXiv Detail & Related papers (2021-06-11T18:00:09Z) - 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.