Structure-Fair Quantum Circuit Complexity: An Auditable Information-Theoretic Lower Bound

• URL: http://arxiv.org/abs/2509.18205v2
• Date: Sun, 19 Oct 2025 10:08:50 GMT
• Title: Structure-Fair Quantum Circuit Complexity: An Auditable Information-Theoretic Lower Bound
• Authors: HongZheng Liu, YiNuo Tian, Zhiyue Wu,
• Abstract summary: This paper introduces the Reference-Contingent Complexity (RCC), an information-theoretic measure calibrated by the available quantum operations.<n>Our central result is a key theorem that rigorously proves the RCC serves as a lower bound for the complexity of any universal quantum circuit.<n>This work provides a "ruler" for quantum technology that is structure-fair and enables cross-platform comparison.
• Score: 0.2606834301724095
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantifying the complexity of quantum states that possess intrinsic structure, such as symmetry or encoding, in a fair manner constitutes a core challenge in the benchmarking of quantum technologies. This paper introduces the Reference-Contingent Complexity (RCC), an information-theoretic measure calibrated by the available quantum operations. The core idea is to leverage the quantum relative entropy to quantify the deviation of a quantum state from its "structured vacuum"-namely, the maximum entropy state within its constrained subspace-thereby only pricing the process of creating non-trivial information. Our central result is a key theorem that rigorously proves the RCC serves as a lower bound for the complexity of any universal quantum circuit. This lower bound is comprised of a linear dominant term, a universal logarithmic correction, and a precise physical correction term that accounts for non-uniformity in the spectral distribution. Crucially, we establish a set of operational protocols, grounded in tasks like quantum hypothesis testing, which make this theoretical lower bound experimentally "auditable." This work provides a "ruler" for quantum technology that is structure-fair and enables cross-platform comparison, thereby establishing a strictly verifiable constraint between the computational cost of the process and the structured information of the final state.

Related papers

• Generalized Gottesman-Kitaev-Preskill States on a Quantum Torus [1.0742675209112622]
  We introduce a novel formulation of a Generalized Gottesman-Kitaev-Preskill (GKP) state that resolves all of its foundational pathologies.<n>We show that these issues are artifacts of defining the code on an unbounded phase-space.<n>This opens a new avenue for fault-tolerant photonic quantum computing.
  arXiv  Detail & Related papers  (2025-09-20T14:56:08Z)
• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [60.996803677584424]
  Variational Quantum Circuits (VQCs) offer a novel pathway for quantum machine learning.<n>Their practical application is hindered by inherent limitations such as constrained linear expressivity, optimization challenges, and acute sensitivity to quantum hardware noise.<n>This work introduces VQC-MLPNet, a scalable and robust hybrid quantum-classical architecture designed to overcome these obstacles.
  arXiv  Detail & Related papers  (2025-06-12T01:38:15Z)
• Quantum complexity in gravity, quantum field theory, and quantum information science [0.0]
  We describe several definitions of complexity, along with their key properties.<n>In quantum many-body systems and quantum field theory (QFT), we discuss a geometric definition of complexity in terms of geodesics on the unitary group.<n>We also outline applications to simple quantum systems, quantum many-body models, and QFTs including conformal field theories (CFTs)
  arXiv  Detail & Related papers  (2025-03-13T18:00:01Z)
• On the Complexity of Quantum Field Theory [0.0]
  We show that from minimal assertions, one is naturally led to measure complexity by two integers, called format and degree.<n>We discuss the physical interpretation of our approach in the context of perturbation theory, symmetries, and the renormalization group.
  arXiv  Detail & Related papers  (2024-10-30T18:00:00Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process. We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2024-05-12T09:05:13Z)
• Quantum benefit of the quantum equation of motion for the strongly coupled many-body problem [0.0]
  The quantum equation of motion (qEOM) is a hybrid quantum-classical algorithm for computing excitation properties of a fermionic many-body system. We demonstrate explicitly that the qEOM exhibits a quantum benefit due to the independence of the number of required quantum measurements.
  arXiv  Detail & Related papers  (2023-09-18T22:10:26Z)
• A simple formulation of no-cloning and no-hiding that admits efficient and robust verification [0.0]
  Incompatibility is a feature of quantum theory that sets it apart from classical theory. The no-hiding theorem is another such instance that arises in the context of the black-hole information paradox. We formulate both of these fundamental features of quantum theory in a single form that is amenable to efficient verification.
  arXiv  Detail & Related papers  (2023-03-05T12:48:11Z)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit. We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
  arXiv  Detail & Related papers  (2023-03-02T18:08:08Z)
• Variational Approach to Quantum State Tomography based on Maximal Entropy Formalism [3.6344381605841187]
  We employ the maximal entropy formalism to construct the least biased mixed quantum state that is consistent with the given set of expectation values. We employ a parameterized quantum circuit and a hybrid quantum-classical variational algorithm to obtain such a target state making our recipe easily implementable on a near-term quantum device.
  arXiv  Detail & Related papers  (2022-06-06T01:16:22Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Circuit Symmetry Verification Mitigates Quantum-Domain Impairments [69.33243249411113]
  We propose circuit-oriented symmetry verification that are capable of verifying the commutativity of quantum circuits without the knowledge of the quantum state. In particular, we propose the Fourier-temporal stabilizer (STS) technique, which generalizes the conventional quantum-domain formalism to circuit-oriented stabilizers.
  arXiv  Detail & Related papers  (2021-12-27T21:15:35Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• The complexity of a quantum system and the accuracy of its description [0.0]
  The complexity of the quantum state of a multiparticle system is connected by a relation similar to the coordinate-momentum uncertainty relation. The coefficient in this relation is equal to the maximum number of qubits whose dynamics can be adequately described by quantum theory.
  arXiv  Detail & Related papers  (2021-05-06T09:16:40Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.