Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order
- URL: http://arxiv.org/abs/2307.10285v3
- Date: Wed, 14 Feb 2024 13:43:55 GMT
- Title: Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order
- Authors: Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau
- Abstract summary: 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.
- Score: 0.9208007322096533
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The standard model of quantum circuits assumes operations are applied in a
fixed sequential "causal" order. In recent years, the possibility of relaxing
this constraint to obtain causally indefinite computations has received
significant attention. The quantum switch, for example, uses a quantum system
to coherently control the order of operations. Several ad hoc computational and
information-theoretical advantages have been demonstrated, raising questions as
to whether advantages can be obtained in a more unified complexity theoretic
framework. In this paper, we approach this problem by studying the query
complexity of Boolean functions under general higher order quantum
computations. To this end, we generalise the framework of query complexity from
quantum circuits to quantum supermaps to compare different models on an equal
footing. We show that the recently introduced class of quantum circuits with
quantum control of causal order cannot lead to any reduction in query
complexity, and that any potential advantage arising from causally indefinite
supermaps can be bounded by the polynomial method, as is the case with quantum
circuits. Nevertheless, 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.
Related papers
- What is computable and non-computable in the quantum domain: 7 statements and 3 conjectures [0.7892577704654171]
There is no universal approach that helps to define a scope of problems that quantum computers are able to speed up.
On the one hand, the class of quantum states that is of interest for quantum computing should be complex.
On the other hand, such quantum states should be reachable on a practical quantum computer.
arXiv Detail & Related papers (2024-03-25T15:47:35Z) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - 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) - Quantum process tomography of continuous-variable gates using coherent
states [49.299443295581064]
We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit.
We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
arXiv Detail & Related papers (2023-03-02T18:08:08Z) - Quantum advantage in temporally flat measurement-based quantum computation [0.0]
We study the efficiency of measurement-based quantum computation with a completely flat temporal ordering of measurements.
We identify a family of Boolean functions for which deterministic evaluation using non-adaptive MBQC is possible.
arXiv Detail & Related papers (2022-12-07T14:34:56Z) - 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) - Experimental violations of Leggett-Garg's inequalities on a quantum
computer [77.34726150561087]
We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems.
Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
arXiv Detail & Related papers (2021-09-06T14:35:15Z) - Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover.
In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z) - Quantum circuits with classical versus quantum control of causal order [0.0]
It is known that quantum supermaps which respect a definite, predefined causal order between their input operations correspond to fixed-order quantum circuits.
Here we identify two new types of circuits that naturally generalise the fixed-order case.
We show that quantum circuits with quantum control of causal order can only generate "causal" correlations, compatible with a well-defined causal order.
arXiv Detail & Related papers (2021-01-21T19:00:06Z) - Quantum State Complexity in Computationally Tractable Quantum Circuits [0.0]
We discuss a special class of numerically tractable quantum circuits, known as quantum automaton circuits.
We show that automaton wave functions have high quantum state complexity.
We present evidence of a linear growth of design complexity in local quantum circuits.
arXiv Detail & Related papers (2020-09-11T16:25:11Z)
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.