Topologically-driven impossibility of superposing unknown states
- URL: http://arxiv.org/abs/2111.02391v2
- Date: Mon, 18 Apr 2022 16:03:33 GMT
- Title: Topologically-driven impossibility of superposing unknown states
- Authors: Zuzana Gavorov\'a
- Abstract summary: A quantum circuit cannot create a superposition from a single copy of each state.
We show that quantum circuits of any sample complexity cannot output a superposition for all input state-pairs.
Considering state tomography we suggest circumventing our impossibility by relaxing to random superposition or entangled superposition.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Impossibilities that are unique to quantum mechanics, such as cloning, can
deepen our physics understanding and lead to numerous applications. One of the
most elementary classical operations is the addition of bit strings. As its
quantum version we can take the task of creating a superposition $\alpha
e^{i\phi(\left|u\right>,\left|v\right>)} \left|u\right>+\beta\left|v\right>$
from two unknown states $\left|u\right>,\left|v\right>\in\mathcal{H}$, where
$\phi$ is some real function and $\alpha,\beta\in\mathbb{C}\setminus\{0\}$.
Oszmaniec, Grudka, Horodecki and W{\'o}jcik [Phys. Rev. Lett. 116(11):110403,
2016] showed that a quantum circuit cannot create a superposition from a single
copy of each state. But how many input copies suffice? Due to quantum
tomography, the sample complexity seems at most exponential. Surprisingly, we
prove that quantum circuits of any sample complexity cannot output a
superposition for all input state-pairs
$\left|u\right>,\left|v\right>\in\mathcal{H}$ - not even when postselection and
approximations are allowed. We show explicitly the limitation on state
tomography that precludes its use for superposition.
Our result is an application of the topological "lower bound" method
[arXiv:2011.10031], which matches any quantum circuit to a continuous function.
We find topological arguments showing that no continuous function can output a
superposition. This new use of the method offers further understanding of its
applicability.
Considering state tomography we suggest circumventing our impossibility by
relaxing to random superposition or entangled superposition. Random
superposition reveals a separation between two types of measurement. Entangled
superposition could still be useful as a subroutine. However, both relaxations
are inspired by the inefficient state tomography. Whether efficient
implementations exist remains open.
Related papers
- Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
We establish connections between state tomography, pseudorandomness, quantum state, circuit lower bounds.
We show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis.
arXiv Detail & Related papers (2024-05-16T16:46:27Z) - 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) - Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle.
We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
arXiv Detail & Related papers (2023-12-23T15:52:46Z) - Provable learning of quantum states with graphical models [4.004283689898333]
We show that certain quantum states can be learned with a sample complexity textitexponentially better than naive tomography.
Our results allow certain quantum states to be learned with a sample complexity textitexponentially better than naive tomography.
arXiv Detail & Related papers (2023-09-17T10:36:24Z) - An efficient quantum algorithm for preparation of uniform quantum
superposition states [0.0]
We show that the superposition state $ketPsi$ can be efficiently prepared with a gate complexity and circuit depth of only $O(logM)$ for all $M$.
Neither ancillabits nor any quantum gates with multiple controls are needed in our approach for creating the uniform superposition state $ketPsi$.
arXiv Detail & Related papers (2023-06-18T17:59:00Z) - Nonlocality under Computational Assumptions [51.020610614131186]
A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations.
We show that there exist (efficient) local producing measurements that cannot be reproduced through randomness and quantum-time computation.
arXiv Detail & Related papers (2023-03-03T16:53:30Z) - Classical shadow tomography for continuous variables quantum systems [13.286165491120467]
We introduce two experimentally realisable schemes for obtaining classical shadows of CV quantum states.
We are able to overcome new mathematical challenges due to the infinite-dimensionality of CV systems.
We provide a scheme to learn nonlinear functionals of the state, such as entropies over any small number of modes.
arXiv Detail & Related papers (2022-11-14T17:56:29Z) - 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) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
We study quantum Ordered Binary Decision Diagrams($OBDD$) model.
We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables.
We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
arXiv Detail & Related papers (2022-04-22T12:37:56Z) - On the Hardness of Detecting Macroscopic Superpositions [3.781421673607643]
We prove that, if one had a quantum circuit to determine if a system was in an equal superposition of two states, one could also swap the two states.
In other words, observing interference between the $|$Alive$rangle$ and $|$Dead$rangle$ states is a "necromancy-hard" problem.
Our results have possible implications for the state dependence of observables in quantum gravity.
arXiv Detail & Related papers (2020-09-16T03:44:12Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
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.