Instantaneous Quantum Computation

Abstract

We examine theoretic architectures and an abstract model for a restricted class of quantum computation, called here instantaneous quantum computation because it allows for essentially no temporal structure within the quantum dynamics. Using the theory of binary matroids, we argue that the paradigm is rich enough to enable sampling from probability distributions that cannot, classically, be sampled from efficiently and accurately. This paradigm also admits simple interactive proof games that may convince a skeptic of the existence of truly quantum effects. Furthermore, these effects can be created using significantly fewer qubits than are required for running Shor's Algorithm.

Significantly rewritten for clarity, more explanation added

References in corpus (8)

• Entropy scaling and simulability by Matrix Product States
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Matchgates and classical simulation of quantum circuits
• Experimental Realization of Deutsch's Algorithm in a One-way Quantum Computer
• On entropy growth and the hardness of simulating time evolution
• One-way Quantum Computation - a tutorial introduction
• Hardness of approximating the weight enumerator of a binary linear code

Cited by in corpus (101)

• Boson Sampling on a Photonic Chip
• Quantum Computational Supremacy
• Random Quantum Circuits
• Strawberry Fields: A Software Platform for Photonic Quantum Computing
• The Expressive Power of Parameterized Quantum Circuits
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Trading classical and quantum computational resources
• Contextuality in Measurement-based Quantum Computation
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Verification of quantum computation: An overview of existing approaches
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Efficient classical simulation of random shallow 2D quantum circuits
• Computational advantage of quantum random sampling
• Efficient Quantum Walk on a Quantum Processor
• Quantum Machine Learning: from physics to software engineering
• Architectures for quantum simulation showing a quantum speedup
• Optimal Blind Quantum Computation
• Verification of Many-Qubit States
• General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
• How many qubits are needed for quantum computational supremacy?
• Continuous-Variable Instantaneous Quantum Computing is hard to sample
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• From estimation of quantum probabilities to simulation of quantum circuits
• Sample complexity of device-independently certified "quantum supremacy"
• Quantum Embedding Search for Quantum Machine Learning
• Progress toward favorable landscapes in quantum combinatorial optimization
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Machine learning \& artificial intelligence in the quantum domain
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Generating a state $t$-design by diagonal quantum circuits
• Simulating complex networks in phase space: Gaussian boson sampling
• Measurement-based classical computation
• Diagonal quantum circuits: their computational power and applications
• Efficient verification of Boson Sampling
• State preparation by shallow circuits using feed forward
• Probabilistic Modeling with Matrix Product States
• Quantum circuits and low-degree polynomials over F_2
• Phase-random states: ensembles of states with fixed amplitudes and uniformly distributed phases in a fixed basis
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Efficient verification of quantum gates with local operations
• Energy-Consumption Advantage of Quantum Computation
• A general framework for phase and interference
• Entanglement and deterministic quantum computing with one qubit
• Correlations for computation and computation for correlations
• Depth-efficient proofs of quantumness
• Diagonal-unitary 2-designs and their implementations by quantum circuits
• Analogue Quantum Simulation: A New Instrument for Scientific Understanding
• A robust W-state encoding for linear quantum optics
• On the sampling complexity of open quantum systems
• Nonadaptive fault-tolerant verification of quantum supremacy with noise
• Simulating Quantum Circuits with Sparse Output Distributions
• The principle of majorization: application to random quantum circuits
• The Computational Complexity of Linear Optics
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
• Commuting quantum circuits: efficient classical simulations versus hardness results
• Robust sparse IQP sampling in constant depth
• The computational power of normalizer circuits over black-box groups
• Quantum Complexity: restrictions on algorithms and architectures
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy
• Accelerating Quantum Algorithms with Precomputation
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Quantum advantage from energy measurements of many-body quantum systems
• Disentangling magic states with classically simulable quantum circuits
• Noise-Adaptive Quantum Compilation Strategies Evaluated with Application-Motivated Benchmarks
• Quantum self-learning Monte Carlo with quantum Fourier transform sampler
• Quantum homomorphic encryption for polynomial-sized circuits
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Quantifying multiparticle entanglement with randomized measurements
• Simulating Quantum Computations with Tutte Polynomials
• Using the Parameterized Quantum Circuit combined with Variational-Quantum-Eigensolver (VQE) to create an Intelligent social workers' schedule problem solver
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• Forging quantum data: classically defeating an IQP-based quantum test
• Sample caching Markov chain Monte Carlo approach to boson sampling simulation
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Differentiating and Integrating ZX Diagrams with Applications to Quantum Machine Learning
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Normalizer Circuits and Quantum Computation
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Dynamic quantum circuit compilation
• On the role of coherence for quantum computational advantage
• Computational quantum-classical boundary of complex and noisy quantum systems
• Passive verification protocol for thermal graph states
• Quantum advantage in temporally flat measurement-based quantum computation
• Simulating quantum computation: how many "bits" for "it"?
• Secret extraction attacks against obfuscated IQP circuits
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• Boson sampling with ultracold atoms in a programmable optical lattice
• Expressiveness of Commutative Quantum Circuits: A Probabilistic Approach
• Speedup in Classical Simulation of Gaussian Boson Sampling
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Sampling and the complexity of nature
• Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable
• Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
• Reduced Sampling Overhead for Probabilistic Error Cancellation by Pauli Error Propagation
• Quantum Circuit Optimization by Graph Coloring
• Quantum states supported by matroids