Quantum advantage with shallow circuits
From MaRDI portal
Abstract: We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem which we call the 2D Hidden Linear Function problem. An instance of the problem is specified by a quadratic form q that maps n-bit strings to integers modulo four. The goal is to identify a linear boolean function which describes the action of q on a certain subset of n-bit strings. We prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the 2D Hidden Linear Function problem with high probability must have depth logarithmic in n. In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates acting locally on a two-dimensional grid.
Recommendations
Cited in
(53)- Computing with a single qubit faster than the computation quantum speed limit
- A proof system for disjoint parallel quantum programs
- Towards quantum computing based community detection
- Quantum random access stored-program machines
- The complexity of quantum circuit mapping with fixed parameters
- Quantum advantage through the magic pentagram problem
- Parrondo's paradox from classical to quantum: a review
- Quantum science and quantum technology
- Power of uninitialized qubits in shallow quantum circuits
- Usefulness of decoherence in quantum-walk-based hash function
- Bell non-locality and Kochen-Specker contextuality: how are they connected?
- Quantum binary search algorithm
- Trading locality for time: certifiable randomness from low-depth circuits
- Experimental pairwise entanglement estimation for an \(N\)-qubit system. A machine learning approach for programming quantum hardware
- Impact of graph structures for QAOA on maxcut
- A generalisation of the phase kick-back
- Barren plateaus from learning scramblers with local cost functions
- The road to quantum computational supremacy
- scientific article; zbMATH DE number 7228448 (Why is no real title available?)
- Revealing advantage in a quantum network
- Quantum advantage for the LOCAL model in distributed computing
- Average-case quantum advantage with shallow circuits
- Understanding the quantum computational speed-up via de-quantisation
- 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time
- Hierarchies of resources for measurement-based quantum computation
- QSW\_MPI: a framework for parallel simulation of quantum stochastic walks
- Uncertainty of feed forward neural networks recognizing quantum contextuality
- An Exact and Practical Classical Strategy for 2D Graph State Sampling
- Quantum advantage in learning from experiments
- Classical and quantum compression for edge computing: the ubiquitous data dimensionality reduction
- Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates
- Quantum nonlocality evolution for two entangled mesoscopic fields under decoherence
- Universal resources for quantum computing
- Evolving quantum circuits
- Quantum computational complexity with photons and linear optics
- Quantum convolutional neural networks for multiclass image classification
- The rank of contextuality
- Quantum algorithm for computing distances between subspaces
- Constant-time quantum algorithm for homology detection in closed curves
- Contextuality and expressivity of non-locality
- Quantum advantage from one-way functions
- The geometry of simplicial distributions on suspension scenarios
- Decoherence and quantum threats in voice biometric authentication with post-quantum countermeasures
- Commutation groups and state-independent contextuality
- Parity vs. \(\text{AC}^0\) with simple quantum preprocessing
- Noisy decoding by shallow circuits with parities: classical and quantum (extended abstract)
- Bridging resource theory and quantum key distribution: geometric analysis and statistical testing
- Quantum federated learning through ancilla-driven quantum computation
- Time-space lower bounds for simulating proof systems with quantum and randomized verifiers
- Triacontagonal proofs of the Bell-Kochen-Specker theorem
- Fundamental limitations on the recoverability of quantum processes
- Benchmarking weak randomness in quantum and natural sources
- Quantum programming in polylogarithmic time
This page was built for publication: Quantum advantage with shallow circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5218670)
