Practical computational advantage from the quantum switch on a generalized family of promise problems
arXiv:2207.12997 · doi:10.22331/q-2023-03-09-945
Abstract
The quantum switch is a quantum computational primitive that provides computational advantage by applying operations in a superposition of orders. In particular, it can reduce the number of gate queries required for solving promise problems where the goal is to discriminate between a set of properties of a given set of unitary gates. In this work, we use Complex Hadamard matrices to introduce more general promise problems, which reduce to the known Fourier and Hadamard promise problems as limiting cases. Our generalization loosens the restrictions on the size of the matrices, number of gates and dimension of the quantum systems, providing more parameters to explore. In addition, it leads to the conclusion that a continuous variable system is necessary to implement the most general promise problem. In the finite dimensional case, the family of matrices is restricted to the so-called Butson-Hadamard type, and the complexity of the matrix enters as a constraint. We introduce the ``query per gate'' parameter and use it to prove that the quantum switch provides computational advantage for both the continuous and discrete cases. Our results should inspire implementations of promise problems using the quantum switch where parameters and therefore experimental setups can be chosen much more freely.
arXiv comment14 pages, 5 figures; more detailed Sections 4 and 5, added new references for section 5, other minor changes
References in corpus (42)
- Quantum correlations with no causal order
- High-dimensional quantum cryptography with twisted light
- Quantum computations without definite causal structure
- General Scheme for Super Dense Coding between Multi-Parties
- Experimental Superposition of Orders of Quantum Gates
- Computational advantage from quantum-controlled ordering of gates
- Experimental Verification of an Indefinite Causal Order
- Enhanced communication with the assistance of indefinite causal order
- Quantum key distribution with higher-order alphabets using spatially-encoded qudits
- Perfect discrimination of no-signalling channels via quantum superposition of causal structures
- Indefinite Causal Order in a Quantum Switch
- Generation of maximally entangled states of qudits using twin photons
- Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
- Quantum Metrology with Indefinite Causal Order
- Experimental transmission of quantum information using a superposition of causal orders
- Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity
- Quantum superposition of the order of parties as a communication resource
- Quantum Refrigeration with Indefinite Causal Order
- Indefinite causal order enables perfect quantum communication with zero capacity channels
- Quantum computation with programmable connections between gates
- Continuous variable quantum computation with spatial degrees of freedom of photons
- Communicating via ignorance: Increasing communication capacity via superposition of order
- Computational advantage from quantum superposition of multiple temporal orders of photonic gates
- Communication Enhancement Through Quantum Coherent Control of Channels in an Indefinite Causal-order Scenario
- Quantum circuits with classical versus quantum control of causal order
- Sending classical information via three noisy channels in superposition of causal orders
- Quantum gravity computers: On the theory of computation with indefinite causal structure
- Experimentally feasible computational advantage from quantum superposition of gate orders
- Noisy quantum metrology with the assistance of indefinite causal order
- Work extraction from coherently activated maps via quantum switch
- Quantum and Classical Data Transmission through Completely Depolarising Channels in a Superposition of Cyclic Orders
- Witnesses of causal nonseparability: an introduction and a few case studies
- Classical Communications with Indefinite Causal Order for completely depolarizing channels
- Semi-device-independent certification of indefinite causal order
- Indefinite causal structures for continuous-variable systems
- Quantum Information Processing by Weaving Quantum Talbot Carpets
- Reassessing the computational advantage of quantum-controlled ordering of gates
- Quantum Circuits for the Unitary Permutation Problem
- Free-Space Entangled Quantum Carpets
- OAM tomography with Heisenberg-Weyl observables
- A Diagrammatic Approach to Information Transmission in Generalised Switches
- Multifold behavior of the information transmission by the quantum 3-switch