Quantum computation with indefinite causal structures

• URL: http://arxiv.org/abs/1706.09854v4
• Date: Wed, 05 Mar 2025 19:17:13 GMT
• Title: Quantum computation with indefinite causal structures
• Authors: Mateus Araújo, Philippe Allard Guérin, Ämin Baumeler,
• Abstract summary: We show that process matrices correspond to a linear particular case of P-CTCs, and therefore that its computational power is upperbounded by that of PP.<n>We show, furthermore, a family of processes that can violate causal inequalities but nevertheless can be simulated by a causally ordered quantum circuit with only a constant overhead.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One way to study the physical plausibility of closed timelike curves (CTCs) is to examine their computational power. This has been done for Deutschian CTCs (D-CTCs) and post-selection CTCs (P-CTCs), with the result that they allow for the efficient solution of problems in PSPACE and PP, respectively. Since these are extremely powerful complexity classes, which are not expected to be solvable in reality, this can be taken as evidence that these models for CTCs are pathological. This problem is closely related to the nonlinearity of this models, which also allows for example cloning quantum states, in the case of D-CTCs, or distinguishing non-orthogonal quantum states, in the case of P-CTCs. In contrast, the process matrix formalism allows one to model indefinite causal structures in a linear way, getting rid of these effects, and raising the possibility that its computational power is rather tame. In this paper we show that process matrices correspond to a linear particular case of P-CTCs, and therefore that its computational power is upperbounded by that of PP. We show, furthermore, a family of processes that can violate causal inequalities but nevertheless can be simulated by a causally ordered quantum circuit with only a constant overhead, showing that indefinite causality is not necessarily hard to simulate.

Related papers

• Unitary Closed Timelike Curves can Solve all of NP [5.475280561991127]
  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.
  arXiv  Detail & Related papers  (2024-10-06T21:28:56Z)
• Quantum state tomography on closed timelike curves using weak measurements [0.0]
  We show that, for any given combination of chronology-respecting input and unitary interaction, it is always possible to recover the unique state on the P-CTC.<n>We also demonstrate how this state may be derived from analysis of the P-CTC prescription itself.
  arXiv  Detail & Related papers  (2024-07-19T17:43:27Z)
• Mapping indefinite causal order processes to composable quantum protocols in a spacetime [0.0]
  We show how the formalism of quantum circuits with quantum control of causal order (QC-QC) connects with the observed composability of physical experiments in spacetime. We incorporate the set-up assumptions of the QC-QC framework into atemporal perspective and show that every QC-QC can be mapped to a causal box. Using a recently introduced concept of fine-graining, we show that the causal box corresponds to a fine-graining of the QC-QC.
  arXiv  Detail & Related papers  (2024-04-08T09:09:50Z)
• Physics-Informed Polynomial Chaos Expansions [7.5746822137722685]
  This paper presents a novel methodology for the construction of physics-informed expansions (PCE) A computationally efficient means for physically constrained PCE is proposed and compared to standard sparse PCE. We show that the constrained PCEs can be easily applied for uncertainty through analytical post-processing.
  arXiv  Detail & Related papers  (2023-09-04T16:16:34Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  We compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. We evaluate their accuracy by providing credible intervals on the quality of the approximation.
  arXiv  Detail & Related papers  (2023-07-17T07:59:47Z)
• Bayes risk CTC: Controllable CTC alignment in Sequence-to-Sequence tasks [63.189632935619535]
  Bayes risk CTC (BRCTC) is proposed to enforce the desired characteristics of the predicted alignment. By using BRCTC with another preference for early emissions, we obtain an improved performance-latency trade-off for online models.
  arXiv  Detail & Related papers  (2022-10-14T03:55:36Z)
• 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)
• Exploring the scaling limitations of the variational quantum eigensolver with the bond dissociation of hydride diatomic molecules [0.0]
  Materials simulations involving strongly correlated electrons pose fundamental challenges to state-of-the-art electronic structure methods. No quantum computer has simulated a molecule of a size and complexity relevant to real-world applications, despite the fact that the variational quantum eigensolver algorithm can predict chemically accurate total energies. We show that the inclusion of d-orbitals and the use of the UCCSD ansatz, which are both necessary to capture the correct TiH physics, dramatically increase the cost of this problem.
  arXiv  Detail & Related papers  (2022-08-15T19:21:17Z)
• 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)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Discovering Latent Causal Variables via Mechanism Sparsity: A New Principle for Nonlinear ICA [81.4991350761909]
  Independent component analysis (ICA) refers to an ensemble of methods which formalize this goal and provide estimation procedure for practical application. We show that the latent variables can be recovered up to a permutation if one regularizes the latent mechanisms to be sparse.
  arXiv  Detail & Related papers  (2021-07-21T14:22:14Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)

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.