Fermionic linear optics corresponds to the dynamics of free fermions and is known to be efficiently simulable classically. We define fermionic anyon models by deforming the fermionic algebra of creation and annihilation operators, and consider the dynamics of number-preserving, quadratic Hamiltonians on these operators. We show that any such deformation results in an anyonic linear-optical model which allows for universal quantum computation.

arXiv:1812.06807Physical Review AJun 27, 20197 citations

Learning fermionic linear optics with Heisenberg scaling and physical operations

Aria Christensen, Andrew Zhao

quant-pharXiv:2602.05058Feb 6, 20260 citations

Quantum Information and Computation

Classical simulation of dissipative fermionic linear optics

BravyiSergey, KönigRobert

Published Nov 1, 2012• 0 citations

Publisher

Abstract

DOI: 10.5555/2481569.2481571

Related papers

Classical simulation of dissipative fermionic linear optics

Sergey B. Bravyi, Robert König

Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of $N$ fermionic modes, our algorithm simulates any such gate in time $O(N^3)$ while a single-mode measurement is simulated in time $O(N^2)$ . The steady state of the Lindblad equation can be computed in time $O(N^3)$ .Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of $N$ fermionic modes, our algorithm simulates any such gate in time $O(N^3)$ while a single-mode measurement is simulated in time $O(N^2)$. The steady state of the Lindblad equation can be computed in time $O(N^3)$.

arXiv:1112.2184Dec 9, 20114 citations

Classical simulation of dissipative fermionic linear optics

Sergey B. Bravyi, Robert König

Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of $N$ ~fermionic modes, our algorithm simulates any such gate in time $O(N^3)$ while a single-mode measurement is simulated in time $O(N^2)$ . The steady state of the Lindblad equation can be computed in time $O(N^3)$ .Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of $N$~fermionic modes, our algorithm simulates any such gate in time $O(N^3)$ while a single-mode measurement is simulated in time $O(N^2)$. The steady state of the Lindblad equation can be computed in time $O(N^3)$.

Quantum Information and ComputationNov 1, 201222 citations

Classical simulation of fermionic linear optics augmented with noisy ancillas

Michał Oszmaniec, Jan Gutt, Marek Kuś

Fermionic linear optics is a model of quantum computation which is efficiently simulable on a classical probabilistic computer. We study the problem of a classical simulation of fermionic linear optics augmented with noisy auxiliary states. If the auxiliary state can be expressed as a convex combination of pure fermionic Gaussian states, the corresponding computation scheme is classically simulable. We present an analytic characterization of the set of convex-Gaussian states in the first nontrivial case, in which the Hilbert space of the ancilla is a four-mode Fock space. We use our result to solve an open problem recently posed by de Melo et al. [New J. Phys. 15, 013015 (2013)] and to study in detail the geometrical properties of the set of convex-Gaussian states.Fermionic linear optics is a model of quantum computation which is efficiently simulable on a classical probabilistic computer. We study the problem of a classical simulation of fermionic linear optics augmented with noisy auxiliary states. If the auxiliary state can be expressed as a convex combination of pure fermionic Gaussian states, the corresponding computation scheme is classically simulable. We present an analytic characterization of the set of convex-Gaussian states in the first nontrivial case, in which the Hilbert space of the ancilla is a four-mode Fock space. We use our result to solve an open problem recently posed by de Melo et al. [New J. Phys. 15, 013015 (2013)] and to study in detail the geometrical properties of the set of convex-Gaussian states.

arXiv:1406.1577Physical Review AAug 28, 201429 citations

Fermionic Linear Optics and Matchgates

Emanuel H. Knill

Fermionic linear optics is efficiently classically simulatable. Here it is shown that the set of states achievable with fermionic linear optics and particle measurements is the closure of a low dimensional Lie group. The weakness of fermionic linear optics and measurements can therefore be explained and contrasted with the strength of bosonic linear optics with particle measurements. An analysis of fermionic linear optics is used to show that the two-qubit matchgates and the simulatable matchcircuits introduced by Valiant generate a monoid of extended fermionic linear optics operators. A useful interpretation of efficient classical simulations such as this one is as a simulation of a model of non-deterministic quantum computation. Problem areas for future investigations are suggested.Fermionic linear optics is efficiently classically simulatable. Here it is shown that the set of states achievable with fermionic linear optics and particle measurements is the closure of a low dimensional Lie group. The weakness of fermionic linear optics and measurements can therefore be explained and contrasted with the strength of bosonic linear optics with particle measurements. An analysis of fermionic linear optics is used to show that the two-qubit matchgates and the simulatable matchcircuits introduced by Valiant generate a monoid of extended fermionic linear optics operators. A useful interpretation of efficient classical simulations such as this one is as a simulation of a model of non-deterministic quantum computation. Problem areas for future investigations are suggested.

arXiv:quant-ph/0108033Aug 7, 200173 citations

Quantum computation from fermionic anyons on a one-dimensional lattice

Allan Tosta, Daniel J. Brod, Ernesto F. Galvão

arXiv:1812.06807Physical Review AJun 27, 20197 citations

Learning fermionic linear optics with Heisenberg scaling and physical operations

Aria Christensen, Andrew Zhao

We revisit the problem of learning fermionic linear optics (FLO), also known as fermionic Gaussian unitaries. Given black-box query access to an unknown FLO, previous proposals required $\widetilde{\mathcal{O}}(n^5 / \varepsilon^2)$ queries, where $n$ is the system size and $\varepsilon$ is the error in diamond distance. These algorithms also use unphysical operations (i.e., violating fermionic superselection rules) and/or $n$ auxiliary modes to prepare Choi states of the FLO. In this work, we establish efficient and experimentally friendly protocols that obey superselection, use minimal ancilla (at most $1$ extra mode), and exhibit improved dependence on both parameters $n$ and $\varepsilon$ . For arbitrary (active) FLOs this algorithm makes at most $\widetilde{\mathcal{O}}(n^4 / \varepsilon)$ queries, while for number-conserving (passive) FLOs we show that $\mathcal{O}(n^3 / \varepsilon)$ queries suffice. The complexity of the active case can be further reduced to $\widetilde{\mathcal{O}}(n^3 / \varepsilon)$ at the cost of using $n$ ancilla. This marks the first FLO learning algorithm that attains Heisenberg scaling in precision. As a side result, we also demonstrate an improved copy complexity of $\widetilde{\mathcal{O}}(n η^2 / \varepsilon^2)$ for time-efficient state tomography of $η$ -particle Slater determinants in $\varepsilon$ trace distance, which may be of independent interest.We revisit the problem of learning fermionic linear optics (FLO), also known as fermionic Gaussian unitaries. Given black-box query access to an unknown FLO, previous proposals required $\widetilde{\mathcal{O}}(n^5 / \varepsilon^2)$ queries, where $n$ is the system size and $\varepsilon$ is the error in diamond distance. These algorithms also use unphysical operations (i.e., violating fermionic superselection rules) and/or $n$ auxiliary modes to prepare Choi states of the FLO. In this work, we establish efficient and experimentally friendly protocols that obey superselection, use minimal ancilla (at most $1$ extra mode), and exhibit improved dependence on both parameters $n$ and $\varepsilon$. For arbitrary (active) FLOs this algorithm makes at most $\widetilde{\mathcal{O}}(n^4 / \varepsilon)$ queries, while for number-conserving (passive) FLOs we show that $\mathcal{O}(n^3 / \varepsilon)$ queries suffice. The complexity of the active case can be further reduced to $\widetilde{\mathcal{O}}(n^3 / \varepsilon)$ at the cost of using $n$ ancilla. This marks the first FLO learning algorithm that attains Heisenberg scaling in precision. As a side result, we also demonstrate an improved copy complexity of $\widetilde{\mathcal{O}}(n η^2 / \varepsilon^2)$ for time-efficient state tomography of $η$-particle Slater determinants in $\varepsilon$ trace distance, which may be of independent interest.

quant-pharXiv:2602.05058Feb 6, 20260 citations

N

fermionic modes, our algorithm simulates any such gate in time

O(N^3)

while a single-mode measurement is simulated in time

O(N^2)

. The steady state of the Lindblad equation can be computed in time

O(N^3)

N

~fermionic modes, our algorithm simulates any such gate in time

O(N^3)

while a single-mode measurement is simulated in time

O(N^2)

. The steady state of the Lindblad equation can be computed in time

O(N^3)

We revisit the problem of learning fermionic linear optics (FLO), also known as fermionic Gaussian unitaries. Given black-box query access to an unknown FLO, previous proposals required

\widetilde{\mathcal{O}}(n^5 / \varepsilon^2)

queries, where

n

is the system size and

\varepsilon

is the error in diamond distance. These algorithms also use unphysical operations (i.e., violating fermionic superselection rules) and/or

n

auxiliary modes to prepare Choi states of the FLO. In this work, we establish efficient and experimentally friendly protocols that obey superselection, use minimal ancilla (at most

1

extra mode), and exhibit improved dependence on both parameters

n

and

\varepsilon

. For arbitrary (active) FLOs this algorithm makes at most

\widetilde{\mathcal{O}}(n^4 / \varepsilon)

queries, while for number-conserving (passive) FLOs we show that

\mathcal{O}(n^3 / \varepsilon)

queries suffice. The complexity of the active case can be further reduced to

\widetilde{\mathcal{O}}(n^3 / \varepsilon)

at the cost of using

n

ancilla. This marks the first FLO learning algorithm that attains Heisenberg scaling in precision. As a side result, we also demonstrate an improved copy complexity of

\widetilde{\mathcal{O}}(n η^2 / \varepsilon^2)

for time-efficient state tomography of

η

-particle Slater determinants in

\varepsilon

trace distance, which may be of independent interest.