The complexity of error metrics

J. D. Franson

Adam R. Brown

This paper proves the polynomial equivalence of a broad class of definitions of quantum computational complexity. We study right-invariant metrics on the unitary group—often called `complexity geometries' following the definition of quantum complexity proposed by Nielsen—and delineate the equivalence class of metrics that have the same computational power as quantum circuits. Within this universality class, any unitary that can be reached in one metric can be approximated in any other metric in the class with a slowdown that is at-worst polynomial in the length and number of qubits and inverse-polynomial in the permitted error. We describe the equivalence classes for two different kinds of error we might tolerate: Killing-distance error, and operator-norm error. All metrics in both equivalence classes are shown to have exponential diameter; all metrics in the operator-norm equivalence class are also shown to give an alternative definition of the quantum complexity class BQP. My results extend those of Nielsen et al., who in 2006 proved that one particular metric is polynomially equivalent to quantum circuits. The Nielsen et al. metric is incredibly highly curved. I show that the greatly enlarged equivalence class established in this paper also includes metrics that have modest curvature. I argue that the modest curvature makes these metrics more amenable to the tools of differential geometry, and therefore makes them more promising starting points for Nielsen's program of using differential geometry to prove complexity lowerbounds. In a previous paper my collaborators and I—inspired by the UV/IR decoupling that happens in the phenomenon of renormalization—conjectured that high- dimensional metrics that look very different at short scales will often nevertheless give rise at long scales to the same emergent effective geometry. The results of this paper provide evidence for those conjectures, since many complexity metrics that have radically different penalty factors and therefore radically different short- distance properties are shown to belong to the same long-distance equivalence class.

Vyacheslav Davydov

We prove equivalence of using the modulus metric and Euclidean metric in solving the soft decoding problem for a memoryless discrete channel with binary input and Q -ary output. For such a channel, we give an example of a construction of binary codes correcting t binary errors in the Hamming metric. The constructed codes correct errors at the output of a demodulator with Q quantization errors as ( t + 1)( Q − 1) − 1 errors in the modulus metric. The obtained codes are shown to have polynomial decoding complexity.

Fabio Benatti

Miruna Roşca, Amin Sakzad, Damien Stehlé +1 more

Jian Qiao, Lizhe Liu, Jinbo Zhang +4 more

In the Shannon Lecture at the 2019 International Symposium on Information Theory (ISIT), Professor Arikan proposed a new coding scheme called polarization-adjusted convolutional (PAC) codes. These codes exhibit excellent error-correction performance for short-to-medium block lengths. Currently, the mainstream decoding algorithms for PAC codes mainly include sequential decoding and list decoding. Fano decoding, a type of sequential decoding, offers good error-correction performance; however, its time complexity is relatively high due to the presence of extensive backtracking processes. In this paper, a fast Fano decoding algorithm based on backtracking optimization mechanism for PAC codes is proposed. The improved algorithm we put forward mitigate the time complexity of the decoding process from two aspects: path backtracking and threshold updating strategy. It enhances the error-correcting performance of the Fano decoding algorithm by introducing the first error node metric and the second error node metric. With the efforts in the above aspects, our decoding algorithm achieves good performance in both complexity and error-correction capability.