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
- Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting.
Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
arXiv Detail & Related papers (2025-02-13T12:04:39Z) - Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits [15.89518426969296]
We investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples.
On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables.
On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed.
arXiv Detail & Related papers (2024-05-21T14:42:39Z) - On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
A feature of constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard.
For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class.
We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be $E = N_mathrmunsat-N_mathrmsat$, spectrally filtered quantum optimization will return states with $E leq q_m.
arXiv Detail & Related papers (2023-12-11T04:15:55Z) - Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order [0.9208007322096533]
We study the query complexity of Boolean functions under general higher order quantum computations.
We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity.
We find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.
arXiv Detail & Related papers (2023-07-18T13:12:55Z) - Quantum Distance Calculation for $\epsilon$-Graph Construction [0.0]
We investigate the potential for quantum advantage in the case of quantum distance calculation for computing $epsilon$-graphs.
We show that, relying on existing quantum multi-state SWAP test based algorithms, the query complexity for correctly identifying two points are not $epsilon$-neighbours is at least O(n3 / ln n)
arXiv Detail & Related papers (2023-06-07T09:43:28Z) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems.
This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state.
Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
arXiv Detail & Related papers (2023-02-07T10:57:36Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees.
Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation.
We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
arXiv Detail & Related papers (2022-03-30T02:02:16Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits.
We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
arXiv Detail & Related papers (2022-03-15T09:46:45Z) - Quantum algorithms for approximate function loading [0.0]
We introduce two approximate quantum-state preparation methods for the NISQ era inspired by the Grover-Rudolph algorithm.
A variational algorithm capable of loading functions beyond the aforementioned smoothness conditions is proposed.
arXiv Detail & Related papers (2021-11-15T17:36:13Z)
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.