On the Reachability Problem in Quantum Petri Nets

• URL: http://arxiv.org/abs/2608.21428v1
• Date: Sun, 16 Aug 2026 21:36:59 GMT
• Title: On the Reachability Problem in Quantum Petri Nets
• Abstract summary: We propose a novel quantum solution to the problem of reachability in bounded quantum Petri nets (QPNs)<n>The proposed approach exploits quantum parallelism to construct a superposition over all reachable markings from the initial marking.<n> Grover's amplitude amplification algorithm is then applied to efficiently identify a desired target marking.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we propose a novel quantum solution to address the problem of reachability in bounded quantum Petri nets (QPNs), an advanced modeling framework that combines the classical Petri net model with quantum mechanical principles. The proposed approach exploits quantum parallelism to construct a superposition over all reachable markings from the initial marking. Grover's amplitude amplification algorithm is then applied to efficiently identify a desired target marking, while ancillary q-tokens used solely for transition control are excluded from the search space, significantly reducing its size. Theoretical analysis shows that our approach achieves a quadratic speed up over classical exhaustive algorithms. Experimental results also confirm the correctness and feasibility of the proposed quantum algorithm for solving the bounded reachability problem in Quantum Petri Nets.

Related papers

• Quantum Optimization Algorithms [1.5571090040924025]
  We motivate and discuss the Quantum Approximate Optimization Algorithm (QAOA), which can be understood as a slightly generalized version of Quantum Annealing for gate-based quantum computers.<n>An example implementation with Pennylane source code demonstrates practical application for the Maximum Cut problem.<n>We outline the Variational Quantum Eigensolver (VQE) as a generalization of the QAOA, highlighting its potential in the NISQ era and addressing challenges such as barren plateaus and ansatz design.
  arXiv  Detail & Related papers  (2025-11-15T22:53:57Z)
• Heisenberg limited quantum algorithm for estimating the fidelity susceptibility [4.524082537369606]
  We present a quantum algorithm that achieves efficient and Heisenberg-limited estimation of fidelity susceptibility.<n>Our work bridges quantum many-body physics and algorithmic design, enabling scalable exploration of quantum criticality.
  arXiv  Detail & Related papers  (2025-09-01T10:56:50Z)
• Evidence of scaling advantage on an NP-Complete problem with enhanced quantum solvers [17.90947220974444]
  We develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem.<n>We experimentally implement our enhanced solvers on a superconducting quantum processor with 13 qubits.<n>Our results provide empirical evidence of quantum speedup for an NP-complete problem.
  arXiv  Detail & Related papers  (2025-08-12T11:52:24Z)
• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [50.95799256262098]
  Variational quantum circuits (VQCs) hold promise for quantum machine learning but face challenges in expressivity, trainability, and noise resilience.<n>We propose VQC-MLPNet, a hybrid architecture where a VQC generates the first-layer weights of a classical multilayer perceptron during training, while inference is performed entirely classically.
  arXiv  Detail & Related papers  (2025-06-12T01:38:15Z)
• Provably Robust Training of Quantum Circuit Classifiers Against Parameter Noise [49.97673761305336]
  Noise remains a major obstacle to achieving reliable quantum algorithms.<n>We present a provably noise-resilient training theory and algorithm to enhance the robustness of parameterized quantum circuit classifiers.
  arXiv  Detail & Related papers  (2025-05-24T02:51:34Z)
• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  We derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models.<n>These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.
  arXiv  Detail & Related papers  (2025-04-25T09:07:55Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem. The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
  arXiv  Detail & Related papers  (2022-05-31T00:14:49Z)
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm [0.0]
  This work proposes a novel approach by using the Quantum Amplitude Damping operation as a resource, in order to construct an efficient quantum algorithm for solving homogeneous LDEs. We show that such an open quantum system-inspired circuitry allows for constructing the real exponential terms in the solution in a non-interferometric.
  arXiv  Detail & Related papers  (2021-11-10T11:25:32Z)
• 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.