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.
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.
We introduce the concept of quantum tensor product expanders. These generalize the concept of quantum expanders, which are quantum maps that are efficient randomizers and use only a small number of Kraus operators. Quantum tensor product expanders 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,
Up to now we have limited ourselves to states of a single particle. In the present chapter we shall introduce the description of two-particle states. Once this case is understood, it will be easy to generalize to any number of particles. States of two (or more) particles lead to very rich configurations called entangled states. A remarkable feature is that two entangled quantum particles, even at arbitrarily large spatial separations, continue to form a single entity and no classical probabilistic model is able to reproduce the correlation between particles. In the first section we shall present the essential mathematical formalism, that of the tensor product. This will permit us in Section 6.2 to describe quantum mixtures using the state operator formalism. Section 6.3 is devoted to the study of important physical consequences like the Bell inequalities and interference experiments involving entangled states, which will lead us to a deeper understanding of quantum physics. Finally, in the last section we shall briefly review applications to measurement theory and quantum information theory. The latter is undergoing rapid development at present and has applications to quantum computing, cryptography, and teleportation. The tensor product of two vector spaces Definition and properties of the tensor product We wish to construct the space of states of two physical systems which we assume initially to be completely independent. Let ℌ N 1 and ℌ M 2 be the spaces of states of the two systems, of dimension N and M , respectively.
Quantum computing is fundamentally based on the mathematical structure of complex Hilbert spaces, linear operators, tensor products, and unitary transformations. Among these concepts, tensor products provide the formal mechanism for constructing the state space of composite quantum systems, whereas linear and unitary operators describe quantum transformations, measurements, and computational gates. This article examines the mathematical relationship between linear operators and tensor products and analyzes their role in the formation, manipulation, and characterization of quantum entanglement. Particular attention is given to two-qubit systems, separable and entangled states, Schmidt decomposition, controlled operations, and the role of non-factorizable operators in quantum circuits. The analysis demonstrates that tensor products perform a dual function: they provide the mathematical representation of composite systems and enable the construction of local operations acting on individual subsystems. At the same time, genuinely entangling transformations, such as the controlled-NOT operation, cannot in general be represented as a single tensor product of independent local operators. Recent research further demonstrates that tensor-product and operator-Schmidt decompositions can be used to characterize operator entanglement, reduce circuit complexity, and construct efficient representations of quantum processes. The results establish that linear algebra and tensor-product structures are not merely formal tools but constitute the mathematical foundation connecting quantum entanglement with quantum computation.