We introduce the concept of quantum tensor product expanders. These are expanders that act on several copies of a given system, where the Kraus operators are tensor products of the Kraus operator on a single system. We begin with the classical case, and show that a classical two-copy expander can be used to produce a quantum expander. We then discuss the quantum case and give applications to the Solovay-Kitaev problem. We give probabilistic constructions in both classical and quantum cases, giving tight bounds on the expectation value of the largest nontrivial eigenvalue in the quantum case.
Abstract In this work we investigate how quantum expanders (i.e., quantum channels with few Kraus operators but a large spectral gap) can be constructed from unitary designs. Concretely, we prove that a random quantum channel whose Kraus operators are independent unitaries sampled from a
2-design measure is with high probability an optimal expander (in the sense that its spectral gap is as large as possible). More generally, we show that, if these Kraus operators are independent unitaries of the form
U⊗k, with
U sampled from a
2k-design measure, then the corresponding random quantum channel is typically an optimal
k-copy tensor product expander, a concept introduced by Harrow and Hastings (Quant. Inf. Comput. 2009).
A classical t-tensor product expander is a natural way of formalising correlated walks of t particles on a regular expander graph. A quantum t-tensor product expander is a completely positive trace preserving map that is a straightforward analogue of a classical t-tensor product expander. Interest in these maps arises from the fact that iterating a quantum t-tensor product expander gives us a unitary t-design, which has many applications to quantum computation and information. We show that the zigzag product of a high dimensional quantum expander (i.e. t = 1) of moderate degree with a moderate dimensional quantum t-tensor product expander of low degree gives us a high dimensional quantum t-tensor product expander of low degree. Previously such a result was known only for quantum expanders i.e. t = 1. Using the zigzag product we give efficient constructions of quantum t-tensor product expanders in dimension D where t = polylog(D). We then show how replacing the zigzag product by the generalised zigzag product leads to almost-Ramanujan quantum tensor product expanders i.e. having near-optimal almost quadratic tradeoff between the degree and the second largest singular value. Both the products give better tradeoffs between the degree and second largest singular value than what was previously known for efficient constructions.
We give a simple recipe for translating walks on Cayley graphs of a group G into a quantum operation on any irrep of G. Most properties of the classical walk carry over to the quantum operation: degree becomes the number of Kraus operators, the spectral gap becomes the gap of the quantum operation (viewed as a linear map on density matrices), and the quantum operation is efficient whenever the classical walk and the quantum Fourier transform on G are efficient. This means that using classical constant-degree constant-gap families of Cayley expander graphs on e.g. the symmetric group, we can construct efficient families of quantum expanders. Background. Classical expanders can be defined in either combinatorial or spectral terms, while quantum expanders usually have only a spectral definition. Quantum expanders were introduced in [2] for their application to quantum spin chains and in [5] for applications to quantum statistical zero knowledge. Here we (following [2] and [4]) define a (N, D, λ) quantum expander to be a quantum operation E that • Has N-dimensional input and output. • Has D Kraus operators. • Has second-largest singular value ≤ λ. Equivalently, if E(ρ) = ρ and tr ρσ = 0 then ‖E(σ)‖2 ≤ λ‖σ‖2,
We discuss a new approach to simulate quantum algorithms using classical probabilistic bits and circuits. Each qubit (a two-level quantum system) is initially mapped to a vector in an eight dimensional probability space (equivalently, to a classical random variable with eight probabilistic outcomes). The key idea in this mapping is to store both the amplitude and phase information of the complex coefficients that describe the qubit state in the probabilities. Due to the identical tensor product structure of combining multiple quantum systems as well as multiple probability spaces,
n qubits are then mapped to a tensor product of
n 8-dimensional probabilistic vectors (i.e., the Hilbert space of dimension
2n is mapped to a probability space of dimension
8n). After this initial mapping, we show how to implement the analogs of single-qubit and two-qubit gates in the probability space using correlation-inducing operations on these classical random variables. The key defining feature of both the mapping to the probability space and the transformations in this space (i.e., operations on the random variables) is that they are not linear, but instead affine. Using this architecture, the evolution of the
2n complex coefficients of the quantum system can be tracked in the joint fully-correlated probabilities of the polynomial number of random variables. We then give specific procedures for implementing (1) the Deutsch-Jozsa algorithm, and (2) the Quantum Fourier Transform in the probability space. Identical to the Quantum case, simulating the Quantum Fourier Transform in the probability space requires
O(n) probabilistic bits and
O(n2) (i.e., quadratic in the number of quantum bits) operations.
Abstract. In this study, we generate quantum channels with random Kraus operators to typically obtain almost twirling quantum channels and quantum expanders. To prove the concentration phenomena, we use matrix Bernstein’s inequality. In this way, our random models do not utilize Haar-distributed unitary matrices or Gaussian matrices. Rather, as in the preceding research, we use unitary t-designs to generate mixed tensor-product unitary channels acting on Cdt. Although our bounds in Schatten p-norm are valid only for 1 ≤p≤ 2, we show that they are typically quantum ϵ-twirling channels with the tail bound proportional to 1/poly(dt), while such bounds were previously constants. The number of required Kraus operators was also improved by powers of logdandt, to be proportional todtlogd/ϵ2. Such random quantum channels are also typically quantum expanders, but the number of Kraus operators must grow proportionally totlogdin our case. Finally, a new non-unital model of super-operators generated by bounded and isotropic random Kraus operators was introduced, which can be typically rectified to yield almost randomizing quantum channels and quantum expanders.