Estimating Traces for Complex Functions Proves Computationally Hard for Classical Computers

Estimating the normalized trace of a function applied to a quantum system becomes computationally difficult when the function possesses an approximate degree of Ω(poly(n)). Zhengfeng Ji from Tsinghua University, Peking University, and the Chinese Academy of Sciences and colleagues have shown that estimating the normalized trace is DQC1-complete under these conditions. The approximate degree dictates how challenging a function is for quantum computers using the DQC1 computational model, offering a general principle for understanding quantum complexity and revealing a connection between a function’s characteristics and potential quantum advantages. Consequently, the approximate degree now defines the boundary separating problems efficiently solved by classical versus quantum computers.

Zhengfeng Ji and colleagues have identified this property as a key parameter for computational difficulty when estimating the normalized trace of a function applied to a quantum system. A smoother, simpler function has a lower degree, while one with many curves and bends has a higher degree; the approximate degree functions similarly, measuring the complexity of a mathematical function. Estimating this normalized trace becomes exceptionally hard, specifically DQC1-complete, when the function’s approximate degree reaches a certain threshold.

Approximate degree dictates quantum speedup for normalised trace estimation

A substantial improvement over previous function-specific analyses has occurred, with normalised trace estimation now possible with a degree of polynomial order, Ω(poly(n)). Previously, a general principle for understanding quantum complexity and linking a function’s characteristics to potential quantum advantages remained elusive. The approximate degree, measuring a function’s complexity, is now central to determining the computational difficulty of normalised trace estimation, revealing its impact on efficient quantum algorithms and potentially demonstrating a significant separation between quantum and classical computational power. Estimating its normalised trace becomes DQC1-complete if a continuous function possesses an approximate degree of Ω(poly(n)), a benchmark of computational hardness within the restricted DQC1 model of quantum computation. This finding extends beyond specific functions, encompassing exponentials, trigonometric functions, logarithms, and inverse functions, demonstrating a general principle at play. Classical computers require exponentially increasing computational power relative to the approximate degree for sparse Hamiltonians. This suggests a potential for substantial quantum speedup

Function complexity dictates classical simulation limits and potential quantum advantage

Developing genuinely useful quantum computers requires understanding the difficulty of estimating properties of quantum systems. ‘Approximate degree’ has been identified as a key factor determining how difficult a calculation is for conventional computers, providing valuable insight into quantum computing limitations. Although the claim of an exponential speedup relies on a currently unproven conjecture regarding the $k$-Forrelation problem, the research clarifies how a function’s complexity dictates classical simulation limits and reveals potential areas where quantum devices can excel. Scientists have identified a key parameter governing how challenging these calculations are for quantum computers by demonstrating DQC1-completeness for functions with a polynomial approximate degree. This clarifies where quantum devices might offer a genuine advantage, efficiently tackling problems intractable for their classical counterparts, even if a full exponential speedup is not ultimately proven. Further investigation will focus on validating this conjecture and exploring the implications for specific quantum algorithms, while the research also explores the limitations of classical simulation, highlighting the exponential increase in computational power required as the approximate degree of the function increases.

The problem addressed concerns the estimation of the normalized trace, mathematically represented as $2^{-n}Tr[f(A)]$, where ‘A’ is a log-local Hamiltonian acting on ‘n’ qubits, and ‘f’ is a given function. The normalized trace represents a crucial quantity in quantum mechanics, often corresponding to the probability of measuring a specific outcome in a quantum system. Estimating this quantity efficiently is vital for various quantum algorithms and simulations. The DQC1 model, a restricted model of quantum computation, is particularly relevant because it is believed to capture the inherent quantum advantages for certain problems, while remaining amenable to theoretical analysis. Establishing DQC1-completeness demonstrates that a problem is as hard as any other problem solvable within that model.

Log-local Hamiltonians are those where interactions between qubits are limited to nearest neighbours, a common assumption in many physical systems. This restriction simplifies the analysis without sacrificing the essential complexity of the problem. The approximate degree of a function ‘f’ essentially quantifies its complexity in terms of polynomial approximations. A function with a low approximate degree can be well-approximated by a low-degree polynomial, while a function with a high approximate degree requires a high-degree polynomial for accurate approximation. This concept is crucial because polynomial approximations are often used in numerical methods for evaluating functions. The research demonstrates that when ‘f’ has an approximate degree of Ω(poly(n)), estimating $2^{-n}Tr[f(A)]$ becomes DQC1-complete, meaning it is computationally intractable for classical computers unless the aforementioned $k$-Forrelation conjecture holds.

The significance of this result lies in its generality. Previous analyses often focused on specific functions, limiting their applicability. This work establishes a general principle based on the approximate degree, providing a framework for understanding the complexity of normalised trace estimation for a broad class of functions. This has implications for the design of quantum algorithms, as it suggests that functions with lower approximate degrees are more amenable to efficient quantum computation. Furthermore, it sheds light on the potential for quantum speedup, indicating that quantum computers may be able to efficiently solve problems that are intractable for classical computers when dealing with functions of sufficient complexity. The finding that classical computers require exponentially increasing resources to simulate these systems with higher approximate degrees reinforces the potential for a substantial quantum advantage.

Methodologically, the researchers employed techniques from quantum information theory and computational complexity to prove the DQC1-completeness result. This involved constructing a reduction from a known DQC1-complete problem to the normalised trace estimation problem, demonstrating that solving the latter would imply solving the former. The technical condition on the polynomial approximation ensures the validity of this reduction. The proof relies on careful analysis of the spectral properties of the Hamiltonian ‘A’ and the function ‘f’, as well as the properties of the DQC1 model. Future research directions include exploring the implications of this result for specific quantum algorithms, such as quantum simulation and quantum machine learning, and investigating the limitations of classical simulation techniques in more detail. Validating the $k$-Forrelation conjecture remains a key open problem, as it would solidify the claim of exponential quantum speedup.

The researchers demonstrated that estimating the normalised trace of a function applied to a log-local Hamiltonian acting on n qubits is DQC1-complete when the function has an approximate degree of Ω(poly(n)). This means the problem is as hard to solve on a quantum computer as any other problem in the DQC1 complexity class. The approximate degree of a function now serves as a key parameter for understanding the computational difficulty of normalised trace estimation, and potentially highlights where quantum computers may outperform classical computers. The authors intend to explore these findings further in the context of quantum simulation and machine learning, alongside attempts to validate a related conjecture about trace estimation.