Certifying Quantum Gates via Automata Advantage

• URL: http://arxiv.org/abs/2510.09575v1
• Date: Fri, 10 Oct 2025 17:29:23 GMT
• Title: Certifying Quantum Gates via Automata Advantage
• Authors: Anna Schroeder, Lucas B. Vieira, Jan Nöller, Nikolai Miklin, Mariami Gachechiladze,
• Abstract summary: We argue that promise problems, studied in the theory of finite automata, provide a natural framework for designing sound tests of quantum gate quality.<n>We show how results from automata theory, in particular the minimality of automata, can be used to derive soundness guarantees.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There is growing interest in developing rigorous tests of quantumness that are feasible even before practical quantum advantages become a reality. Such tests not only aim to certify the quantum nature of a system but also serve as benchmarks for precise quantum control. In this work, we argue that promise problems, studied in the theory of finite automata, provide a natural framework for designing sound tests of quantum gate quality. Soundness, the property that only implementations of sufficiently high quality can pass the test, is a central requirement for meaningful certification. We study several promise problems relevant to quantum gate testing and establish separations between the memory resources required by quantum and classical finite automata to solve them. These separations form the theoretical basis for using promise problems as tests of quantumness. Finally, we show how results from automata theory, in particular the minimality of automata, can be used to derive soundness guarantees.

Related papers

• Digital quantum simulation of many-body systems: Making the most of intermediate-scale, noisy quantum computers [51.56484100374058]
  This thesis is centered around simulating quantum dynamics on quantum devices.<n>We present an overview of the most relevant quantum algorithms for quantum dynamics.<n>We identify relevant problems within quantum dynamics that could benefit from quantum simulation in the near future.
  arXiv  Detail & Related papers  (2025-08-29T10:37:19Z)
• Context-Aware Unit Testing for Quantum Subroutines [14.117812847408523]
  Testing quantum software presents unique challenges due to the non-deterministic nature of quantum information, the high dimensionality of the underlying Hilbert space, complex hardware noise, and the inherent non-local properties of quantum systems.<n>We propose incorporating context-awareness into the testing process to address the computational complexity associated with unit testing in quantum systems.
  arXiv  Detail & Related papers  (2025-06-12T04:58:56Z)
• Sound certification of memory-bounded quantum computers [0.1874930567916036]
  We introduce an approach, which we call quantum system quizzing, for the certification of quantum gates in a practical server-user scenario.<n> Importantly, this approach does not require trusted state preparation and measurement and is thus inherently free from the associated systematic errors.<n>A major technical challenge that we are first to resolve in the memory-bounded single-device setup is recovering the tensor product structure of a multi-qubit system.
  arXiv  Detail & Related papers  (2024-11-06T19:23:45Z)
• Classical certification of quantum gates under the dimension assumption [0.1874930567916036]
  We introduce a certification method for quantum gates tailored for a practical server-user scenario.<n>For single-qubit gates, including those that form a universal set for single-qubit quantum computation, we demonstrate that our approach offers soundness guarantees.
  arXiv  Detail & Related papers  (2024-01-30T13:40:39Z)
• Classical Verification of Quantum Learning [42.362388367152256]
  We develop a framework for classical verification of quantum learning. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents.
  arXiv  Detail & Related papers  (2023-06-08T00:31:27Z)
• Quantum-Error-Mitigation Circuit Groups for Noisy Quantum Metrology [0.0]
  Quantum technologies work by utilizing properties inherent in quantum systems such as quantum coherence and quantum entanglement. Quantum technologies are fragile against an interaction with an environment (decoherence) and in order to utilize them with high accuracy we need to develop error mitigation techniques.
  arXiv  Detail & Related papers  (2023-03-03T10:01:42Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Test of Quantumness with Small-Depth Quantum Circuits [1.90365714903665]
  Recently, we have shown how to construct a test of quantumness based on the learning with errors (LWE) assumption. This test has lead to several cryptographic applications. In this paper, we show that this test of quantumness, and essentially all the above applications, can actually be implemented by a very weak class of quantum circuits.
  arXiv  Detail & Related papers  (2021-05-12T08:16:20Z)
• Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
  We show that the advantage of quantum kernels is vanished for large size datasets, few number of measurements, and large system noise. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
  arXiv  Detail & Related papers  (2021-03-31T02:41:36Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• On the learnability of quantum neural networks [132.1981461292324]
  We consider the learnability of the quantum neural network (QNN) built on the variational hybrid quantum-classical scheme. We show that if a concept can be efficiently learned by QNN, then it can also be effectively learned by QNN even with gate noise.
  arXiv  Detail & Related papers  (2020-07-24T06:34:34Z)

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.