stateQIP = statePSPACE
- URL: http://arxiv.org/abs/2301.07730v2
- Date: Mon, 10 Apr 2023 17:12:10 GMT
- Title: stateQIP = statePSPACE
- Authors: Tony Metger, Henry Yuen
- Abstract summary: We study the relation between two such state classes:SDPPSPACE, and stateQIP.
Our main result is the reverse inclusion, stateQIP $subseteq$ statePSPACE.
We also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum space.
- Score: 0.15229257192293197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Complexity theory traditionally studies the hardness of solving classical
computational problems. In the quantum setting, it is also natural to consider
a different notion of complexity, namely the complexity of physically preparing
a certain quantum state. We study the relation between two such state
complexity classes: statePSPACE, which contains states that can be generated by
space-uniform polynomial-space quantum circuits, and stateQIP, which contains
states that a polynomial-time quantum verifier can generate by interacting with
an all-powerful untrusted quantum prover. The latter class was recently
introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE
$\subseteq$ stateQIP.
Our main result is the reverse inclusion, stateQIP $\subseteq$ statePSPACE,
thereby establishing equality of the two classes and providing a natural
state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et
al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum
algorithm for solving a large class of exponentially large "PSPACE-computable"
semidefinite programs (SDPs), which also prepares an optimiser encoded in a
quantum state. Our SDP solver relies on recent block-encoding techniques from
quantum algorithms, demonstrating that these techniques are also useful for
complexity theory.
Using similar techniques, we also show that optimal prover strategies for
general quantum interactive protocols can be implemented in quantum polynomial
space. We prove this by studying an algorithmic version of Uhlmann's theorem
and establishing an upper bound on the complexity of implementing Uhlmann
transformations.
Related papers
- Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process.
We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable.
Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs.
We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
arXiv Detail & Related papers (2024-05-12T09:05:13Z) - Towards Quantum Computational Mechanics [1.7201069233638664]
We show how quantum computing can be used to solve representative volume element (RVE) problems in computational homogenisation.
Our quantum RVE solver attains exponential acceleration with respect to classical solvers.
arXiv Detail & Related papers (2023-12-06T12:53:02Z) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry.
We present a survey of several potential application areas of quantum algorithms.
We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z) - Quantum Signal Processing with the one-dimensional quantum Ising model [0.0]
Quantum Signal Processing (QSP) has emerged as a promising framework to manipulate and determine properties of quantum systems.
We provide examples and applications of our approach in diverse fields ranging from space-time dual quantum circuits and quantum simulation, to quantum control.
arXiv Detail & Related papers (2023-09-08T18:01:37Z) - Unitary Complexity and the Uhlmann Transformation Problem [41.67228730328207]
We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes.
We use this framework to study the complexity of transforming one entangled state into another via local operations.
Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
arXiv Detail & Related papers (2023-06-22T17:46:39Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - Quantum Merlin-Arthur proof systems for synthesizing quantum states [0.0]
We investigate a state synthesizing counterpart of the class NP-synthesizing.
We establish that the family of UQMA witnesses, considered as one of the most natural candidates, is in stateQMA.
We demonstrate that stateQCMA achieves perfect completeness.
arXiv Detail & Related papers (2023-03-03T12:14:07Z) - Quantum process tomography of continuous-variable gates using coherent
states [49.299443295581064]
We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit.
We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
arXiv Detail & Related papers (2023-03-02T18:08:08Z) - Interactive Proofs for Synthesizing Quantum States and Unitaries [0.15229257192293197]
We study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations.
We define models of interactive proofs for quantum states and unitaries.
We obtain analogous results in the setting with multiple entangled provers as well.
arXiv Detail & Related papers (2021-08-16T15:59:33Z) - Detailed Account of Complexity for Implementation of Some Gate-Based
Quantum Algorithms [55.41644538483948]
In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself.
We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
arXiv Detail & Related papers (2021-06-23T16:33:33Z)
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.