Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states

• URL: http://arxiv.org/abs/2012.15825v2
• Date: Tue, 23 Nov 2021 15:08:45 GMT
• Title: Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Authors: Micha{\l} Oszmaniec, Ninnat Dangniam, Mauro E.S. Morales, Zolt\'an Zimbor\'as
• Abstract summary: We show that Fermionic Linear Optics (FLO) circuits can be used to demonstrate quantum computational advantage with strong hardness guarantees. We consider in parallel two classes of circuits: particle-number conserving (passive) FLO and active FLO that preserves only fermionic parity.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fermionic Linear Optics (FLO) is a restricted model of quantum computation which in its original form is known to be efficiently classically simulable. We show that, when initialized with suitable input states, FLO circuits can be used to demonstrate quantum computational advantage with strong hardness guarantees. Based on this, we propose a quantum advantage scheme which is a fermionic analogue of Boson Sampling: Fermion Sampling with magic input states. We consider in parallel two classes of circuits: particle-number conserving (passive) FLO and active FLO that preserves only fermionic parity and is closely related to Matchgate circuits introduced by Valiant. Mathematically, these classes of circuits can be understood as fermionic representations of the Lie groups $U(d)$ and $SO(2d)$. This observation allows us to prove our main technical results. We first show anticoncentration for probabilities in random FLO circuits of both kind. Moreover, we prove robust average-case hardness of computation of probabilities. To achieve this, we adapt the worst-to-average-case reduction based on Cayley transform, introduced recently by Movassagh, to representations of low-dimensional Lie groups. Taken together, these findings provide hardness guarantees comparable to the paradigm of Random Circuit Sampling. Importantly, our scheme has also a potential for experimental realization. Both passive and active FLO circuits are relevant for quantum chemistry and many-body physics and have been already implemented in proof-of-principle experiments with superconducting qubit architectures. Preparation of the desired quantum input states can be obtained by a simple quantum circuit acting independently on disjoint blocks of four qubits and using 3 entangling gates per block. We also argue that due to the structured nature of FLO circuits, they can be efficiently certified.

Related papers

• Fermionic Averaged Circuit Eigenvalue Sampling [0.0]
  FACES is a protocol to simultaneously learn the averaged error rates of many fermionic linear optical (FLO) gates. We rigorously show that our protocol has an efficient sampling complexity, owing in-part to useful properties of the Kravchuk transformations.
  arXiv  Detail & Related papers  (2025-04-02T17:46:16Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
  A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass. Existing single-round protocols require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. We construct efficient single-round proofs of quantumness based on existing knowledge assumptions.
  arXiv  Detail & Related papers  (2024-05-24T17:33:10Z)
• Quantum simulation of Fermi-Hubbard model based on transmon qudit interaction [0.0]
  We introduce a novel quantum simulation approach utilizing qudits to overcome such complexities. We first demonstrate a Qudit Fermionic Mapping (QFM) that reduces the encoding cost associated with the qubit-based approach. We then describe the unitary evolution of the mapped Hamiltonian by interpreting the resulting Majorana operators in terms of physical single- and two-qudit gates.
  arXiv  Detail & Related papers  (2024-02-02T09:10:40Z)
• Fermionic quantum processing with programmable neutral atom arrays [0.539215791790606]
  Simulating the properties of many-body fermionic systems is an outstanding computational challenge relevant to material science, quantum chemistry, and particle physics. We present a fermionic quantum processor, where fermionic models are encoded in a fermionic register and simulated in a hardware-efficient manner using fermionic gates.
  arXiv  Detail & Related papers  (2023-03-13T10:35:48Z)
• Efficient estimation of trainability for variational quantum circuits [43.028111013960206]
  We find an efficient method to compute the cost function and its variance for a wide class of variational quantum circuits. This method can be used to certify trainability for variational quantum circuits and explore design strategies that can overcome the barren plateau problem.
  arXiv  Detail & Related papers  (2023-02-09T14:05:18Z)
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation [1.433758865948252]
  We show how to design MPFs that do not amplify the hardware and sampling errors, and demonstrate their performance. We observe an error reduction of up to an order of magnitude when compared to a product formula approach by suppressing hardware noise with Pauli Twirling, pulse efficient transpilation, and a novel zero-noise extrapolation based on scaled cross-resonance pulses.
  arXiv  Detail & Related papers  (2022-07-22T18:00:05Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Quantifying fermionic nonlinearity of quantum circuits [0.5658123802733283]
  We quantify the classical simulatability of quantum circuits designed for simulating fermionic Hamiltonians. We find that, depending on the error probability and atomic spacing, there are regions where the fermionic nonlinearity becomes very small or unity.
  arXiv  Detail & Related papers  (2021-11-29T15:31:43Z)
• Learnability of the output distributions of local quantum circuits [53.17490581210575]
  We investigate, within two different oracle models, the learnability of quantum circuit Born machines. We first show a negative result, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable. We show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable.
  arXiv  Detail & Related papers  (2021-10-11T18:00:20Z)
• Preparation of excited states for nuclear dynamics on a quantum computer [117.44028458220427]
  We study two different methods to prepare excited states on a quantum computer. We benchmark these techniques on emulated and real quantum devices. These findings show that quantum techniques designed to achieve good scaling on fault tolerant devices might also provide practical benefits on devices with limited connectivity and gate fidelity.
  arXiv  Detail & Related papers  (2020-09-28T17:21:25Z)
• Efficient quantum circuits for quantum computational chemistry [0.0]
  Efficient ways to perform fermionic excitations are vital for the realization of the variational quantum eigensolver (VQE) on noisy intermediate-scale quantum computers. We demonstrate circuits that perform qubit excitations, excitations that do not account for fermionic anticommutation relations. Compared to circuits constructed with the standard use of "$CNOT$ staircases," our circuits offer a linear reduction in the number of $CNOT$ gates.
  arXiv  Detail & Related papers  (2020-05-29T09:46:23Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

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.