Unitary Closed Timelike Curves can Solve all of NP

• URL: http://arxiv.org/abs/2410.04630v1
• Date: Sun, 6 Oct 2024 21:28:56 GMT
• Title: Unitary Closed Timelike Curves can Solve all of NP
• Authors: Omri Shmueli,
• Abstract summary: We show that $mathbfBQP_ell CTC$ contains tasks that are outside $mathbfBQP$. Our work shows that non-linearity is what enables CTCs to solve $mathbfNP$, is false, and raises the importance of understanding whether purifiable process matrices are physical or not.
• Score: 5.475280561991127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Born in the intersection between quantum mechanics and general relativity, indefinite causal structure is the idea that in the continuum of time, some sets of events do not have an inherent causal order between them. Process matrices, introduced by Oreshkov, Costa and Brukner (Nature Communications, 2012), define quantum information processing with indefinite causal structure -- a generalization of the operations allowed in standard quantum information processing, and to date, are the most studied such generalization. Araujo et al. (Physical Review A, 2017) defined the computational complexity of process matrices, and showed that polynomial-time process matrix computation is equivalent to standard polynomial-time quantum computation with access to a weakening of post-selection Closed Timelike Curves (CTCs), that are restricted to be $\textit{linear}$. Araujo et al. accordingly defined the complexity class for efficient process matrix computation as $\mathbf{BQP}_{\ell CTC}$ (which trivially contains $\mathbf{BQP}$), and posed the open question of whether $\mathbf{BQP}_{\ell CTC}$ contains computational tasks that are outside $\mathbf{BQP}$. In this work we solve this open question under a widely believed hardness assumption, by showing that $\mathbf{NP} \subseteq \mathbf{BQP}_{\ell CTC}$. Our solution is captured by an even more restricted subset of process matrices that are purifiable (Araujo et al., Quantum, 2017), which (1) is conjectured more likely to be physical than arbitrary process matrices, and (2) is equivalent to polynomial-time quantum computation with access to $\textit{unitary}$ (which are in particular linear) post-selection CTCs. Conceptually, our work shows that the previously held belief, that non-linearity is what enables CTCs to solve $\mathbf{NP}$, is false, and raises the importance of understanding whether purifiable process matrices are physical or not.

Related papers

• Quantum computational complexity of matrix functions [2.7488316163114823]
  We study the computational complexity of two primitive problems. We consider four functions -- monomials, Chebyshevs, the time evolution function, and the inverse function.
  arXiv  Detail & Related papers  (2024-10-17T18:00:03Z)
• Finding quantum partial assignments by search-to-decision reductions [0.0]
  We show that a quantum algorithm with access to a $mathsfQMA$ oracle can construct $mathsfQMA$ witnesses as quantum states. We prove that if one is not interested in the quantum witness as a quantum state but only in terms of its partial assignments, then there exists a classical-time algorithm with access to a $mathsfQMA$ oracle.
  arXiv  Detail & Related papers  (2024-08-07T18:00:00Z)
• Efficient Unitary T-designs from Random Sums [0.6640968473398456]
  Unitary $T$-designs play an important role in quantum information, with diverse applications in quantum algorithms, benchmarking, tomography, and communication. We provide a new construction of $T$-designs via random matrix theory using $tildeO(T2 n2)$ quantum gates.
  arXiv  Detail & Related papers  (2024-02-14T17:32:30Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• 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)
• An Improved Classical Singular Value Transformation for Quantum Machine Learning [2.3326951882644553]
  We study quantum speedups in quantum machine learning (QML) by analyzing the quantum singular value transformation (QSVT) framework. Our key insight is to combine the Clenshaw recurrence, an iterative method for computing matrix stability, with sketching techniques to simulate QSVT classically.
  arXiv  Detail & Related papers  (2023-03-02T18:53:03Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)
• 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.