Quantum computations are typically performed as a sequence of basic operations, called quantum gates. Different gate sequences, called quantum circuits, can implement the same overall quantum computation. Since every additional quantum gate takes time and introduces noise into the system, it is important to find the smallest possible quantum circuit that implements a given computation, especially for near-term quantum devices that can execute only a limited number of quantum gates before noise renders the computation useless. An important building block for many quantum circuit optimization techniques is pattern matching: given a large and small quantum circuit, we would like to find all maximal matches of the small circuit, called a pattern , in the large circuit, considering pairwise commutation of quantum gates. In this work, we present the first classical algorithm for pattern matching that provably finds all maximal matches and is efficient enough to be practical for circuit sizes typical for near-term devices. We demonstrate numerically 1 that combining our algorithm with known pattern-matching-based circuit optimization techniques reduces the gate count of a random quantum circuit by ∼ 30% and can further improve practically relevant quantum circuits that were already optimized with state-of-the-art techniques.

The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorousa priorianda posterioribounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments.

We generalize alternating optimization algorithms of Blahut-Arimoto type to the quantum setting. In particular, we give iterative algorithms to compute the mutual information of quantum channels, the thermodynamic capacity of quantum channels, the coherent information of less noisy quantum channels, and the Holevo quantity of classical-quantum channels. Our convergence analysis is based on quantum entropy inequalities and leads to a priori additive ε-approximations after O (ε-1log N) iterations, where N denotes the input dimension of the channel. We complement our analysis with an a posteriori stopping criterion which allows us to terminate the algorithm after significantly fewer iterations compared to the a priori criterion in numerical examples. Finally, we discuss heuristics to accelerate the convergence.

Quantum generalizations of Rényi's entropies are a useful tool to describe a variety of operational tasks in quantum information processing. Two families of such generalizations turn out to be particularly useful: the Petz quantum Rényi divergence D̅αand the minimal quantum Rényi divergence D̅α. In this paper, we prove a reverse Araki-Lieb-Thirring inequality that implies a new relation between these two families of divergences, namely that αD̅α(ρ∥σ) ≤ D̅α(ρ∥σ) for α ϵ [0, 1] and where ρ and σ are density operators. This bound suggests defining a “pretty good fidelity”, whose relation to the usual fidelity implies the known relations between the optimal and pretty good measurement as well as the optimal and pretty good singlet fraction.

Quantum generalizations of Rényi's entropies are a useful tool to describe a variety of operational tasks in quantum information processing. Two families of such generalizations turn out to be particularly useful: the Petz quantum Rényi divergence D̅αand the minimal quantum Rényi divergence D̃α. In this paper, we prove a reverse Araki-Lieb-Thirring inequality that implies a new relation between these two families of divergences, namely, αD̅α(Q∥σ) ≤ D̃α(Q∥σ) for α ∈[0,1] and where Q and σ are density operators. This bound suggests defining a ”pretty good fidelity,” whose relation to the usual fidelity implies the known relations between the optimal and pretty good measurement as well as the optimal and pretty good singlet fraction. We also find a new necessary and sufficient condition for optimality of the pretty good measurement and singlet fraction.