Efficient Algorithms for Causal Order Discovery in Quantum Networks
- URL: http://arxiv.org/abs/2012.01731v3
- Date: Tue, 28 Sep 2021 04:46:27 GMT
- Title: Efficient Algorithms for Causal Order Discovery in Quantum Networks
- Authors: Ge Bai, Ya-Dong Wu, Yan Zhu, Masahito Hayashi, Giulio Chiribella
- Abstract summary: Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm.
We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with.
Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
- Score: 44.356294905844834
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given black-box access to the input and output systems, we develop the first
efficient quantum causal order discovery algorithm with polynomial query
complexity with respect to the number of systems. We model the causal order
with quantum combs, and our algorithms output the order of inputs and outputs
that the given process is compatible with. Our algorithm searches for the last
input and the last output in the causal order, removes them, and iteratively
repeats the above procedure until we get the order of all inputs and outputs.
Our method guarantees a polynomial running time for quantum combs with a low
Kraus rank, namely processes with low noise and little information loss. For
special cases where the causal order can be inferred from local observations,
we also propose algorithms that have lower query complexity and only require
local state preparation and local measurements. Our algorithms will provide
efficient ways to detect and optimize available transmission paths in quantum
communication networks, as well as methods to verify quantum circuits and to
discover the latent structure of multipartite quantum systems.
Related papers
- Quantum Multiplexer Simplification for State Preparation [0.7270112855088837]
We propose an algorithm that detects whether a given quantum state can be factored into substates.
The simplification is done by eliminating controls of quantum multiplexers.
Considering efficiency in terms of depth and number of CNOT gates, our method is competitive with the methods in the literature.
arXiv Detail & Related papers (2024-09-09T13:53:02Z) - Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
Currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices.
We propose a novel method that can improve variational quantum algorithms -- discretized quantum exhaustive search''
arXiv Detail & Related papers (2024-07-24T22:06:05Z) - 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) - Optimization of probabilistic quantum search algorithm with a priori
information [0.21756081703276003]
Grover's quantum search algorithm is a typical quantum algorithm that proves the superiority of quantum computing over classical computing.
We consider a probabilistic Grover search algorithm allowing nonzero probability of failure for a database with a general a priori probability distribution of the elements.
arXiv Detail & Related papers (2023-04-06T04:33:37Z) - 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) - 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) - Parametrized Complexity of Quantum Inspired Algorithms [0.0]
Two promising areas of quantum algorithms are quantum machine learning and quantum optimization.
Motivated by recent progress in quantum technologies and in particular quantum software, research and industrial communities have been trying to discover new applications of quantum algorithms.
arXiv Detail & Related papers (2021-12-22T06:19:36Z) - Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases.
We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
arXiv Detail & Related papers (2021-07-03T16:07:30Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
We propose a novel hardware efficient quantum search algorithm to overcome this challenge.
Our key idea is to replace the global diffusion operation with low-cost local diffusions.
The circuit cost reduction leads to a remarkable improvement in the system success rates.
arXiv Detail & Related papers (2021-03-26T01:08:50Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z)
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.