In this work, we prove a lower bound on the difference between the first and second singular values of quantum channels induced by random isometries, that is tight in the scaling of the number of Kraus operators. This allows us to give an upper bound on the difference between the first and second largest (in modulus) eigenvalues of random channels with same large input and output dimensions for finite number of Kraus operators
k≥169. Moreover, we show that these random quantum channels are quantum expanders, answering a question posed by Hastings. As an application, we show that ground states of infinite 1D spin chains, which are well-approximated by matrix product states, fulfill a principle of maximum entropy.
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).
With unitary coin operator that is a random matrix drawn from a uniform distribution with respect to the Haar measure, we construct a variant of a discrete quantum random walk using a d-regular undirected connected simple graph. With each step of the walk, the coin operator random matrix is drawn independently from the distribution. The expectation value over the distribution of random unitaries for the associated quantum channel gives a depolarization channel for the coin subspace and resembles the associated classical random walk where the direction a walker steps depends upon the outcome of a fair coin or balanced d-sided dice. Remarkably, despite the fact that the averaged channel depolarizes the coin subspace, measurements in the vertex subspace can be designed that would reveal information about the initial quantum state, even after many iterations of the channel. We illustrate with examples of quantum walks on Cayley graphs of Abelian groups, such as the cycle and hypercube graphs. For Cayley graphs of Abelian groups, the averaged channel is dephasing in the Fourier basis. These quantum walks are examples of bipartite strongly interacting systems, where one subsystem is strongly perturbed, yet information about the initial state in the other subsystem is potentially measurable forever. Due to its decoherence, a quantum random walk with a Haar-random coin would not be useful in search algorithms but could aid in understanding quantum systems with strongly perturbed subsystems.
We analyze the quantum capacity of a unital quantum channel, using ideas from the proof of near-optimality of Petz recovery map [Barnum and Knill 2000] and give an upper bound on the quantum capacity in terms of regularized output 2-norm of the channel. We also show that any code attempting to exceed this upper bound must incur large error in decoding, which can be viewed as a weaker version of the strong converse results for quantum capacity. As an application, we find nearly matching upper and lower bounds (up to an additive constant) on the quantum capacity of quantum expander channels. Using these techniques, we further conclude that the `mixture of random unitaries' channels arising in the construction of quantum expanders in [Hastings 2007] show a trend in multiplicativity of output 2-norm similar to that exhibited in [Montanaro 2013] for output œ-norm of random quantum channels.
We prove constant lower bounds for the spectral gap of the following random walks on unitary groups
SU(2n) on
n qubits. (i) Random Pauli Rotation: choose an
n-qubit Pauli operator
P and an angle
θ∈[0,2π), both uniformly at random, and apply
eiθP. (ii) Brickwork Random Unitary Circuit: choose
n−1 unitaries
Ui uniformly at random from
SU(4) (including central phases of the parent group) independently, and apply
U2j−1 on two qubits
2j−1,2j and then
U2j on two qubits
2j,2j+1. Importantly, the gap bounds are independent of
n and apply for all finite dimensional unitary representations of
SU(2n) uniformly.
Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary
t-designs after
O(nt) steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be
O(2cn) for some
c<1. Our unconditional constant spectral gap removes this restriction.
We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal
t-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for
t=2.