Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physics of Particles and Nuclei Letters

Optical device accelerating dynamic programming

Dima Yu. Grigoriev, Alexander Ya. Kazakov, S. Vakulenko

Published Mar 1, 2007• 1 citation
Publisher

Abstract

The subject of this report is the comparison of the conventional deterministic computers versus the analogue computer based on the quantum optical system in resolving some NP-hard computational problems. We describe an optical machine which can be realized physically.
DOI
10.1134/s1547477107020094

Related papers

Nondeterministic Logic Gates in Optical Quantum Computing

Hwang Lee, Jonathan P. Dowling, Federico M. Spedalieri

Chapman & Hall/CRC applied mathematics and nonlinear science series•Sep 19, 2007•0 citations

Quantum optical device accelerating dynamic programming

Dima Yu. Grigoriev, Alexander Ya. Kazakov, S. A. Vakulenko

In this paper we discuss analogue computers based on quantum optical systems accelerating dynamic programming for some computational problems. These computers, at least in principle, can be realized by actually existing devices. We estimate an acceleration in resolving of some NP-hard problems that can be obtained in such a way versus deterministic computers

arXiv:quant-ph/0506081•Jun 10, 2005•0 citations

Optical implementation of quantum computers

John Rarity, Harald Weinfurter

Journal of Optics B Quantum and Semiclassical Optics•Sep 15, 2004•0 citations

The Ising Machine as a Physical Non-Deterministic Computing Device: Formal Proof, Polynomial-Time Equivalence for NP, and Cryptographic Implications at Scale

Kaoru Aguilera Katayama

We present a rigorous, self-contained proof that an idealised Ising Machine (IM)-defined axiomatically from the experimentally observed properties of coherent Ising machines (CIMs), quantum annealers, and memristive/optical Ising processors-satisfies every clause of the canonical definition of a non-deterministic computing device in the sense of Turing (1936), Rabin and Scott (1959), and Cook (1971). Concretely, we show that (i) The physical ground-state search performed by an N-spin Ising Machine is not a deterministic computation: the machine simultaneously and physically explores an exponential number of spin configurations, and the branch that is "selected" (the ground state) is not the output of any single deterministic trajectory. (ii) There exists a polynomial-time simulation of any non-deterministic Turing machine (NDTM) by a suitably scaled Ising Machine, and conversely, every Ising Machine computation can be simulated by an NDTM in polynomial time. Hence the Ising Machine decides exactly the class NP in polynomial physical time. (iii) Because NP is, by definition, the class of languages decidable in polynomial time on a non-deterministic machine, a scalable Ising Machine would solve every NP problem in polynomial time, rendering all cryptographic schemes whose security relies on NP-hard or presumed-intractable problems (RSA, ECC, lattice-based, subset-sum-based, code-based, etc.) insecure. The argument is structured axiomatically: we first isolate the minimal physical axioms an Ising Machine must satisfy, then construct a formal mapping to the NDTM model, and finally derive the complexity-theoretic and cryptographic consequences. We discuss the crucial role of the scalability assumption and the engineering gap that currently prevents the full realisation of the threat.

•Mar 24, 2026•0 citations

Quadrature Photonic Spatial Ising Machine

Wenjia Zhang, Wencheng Sun, Yuanyuan Liu +3 more

Abstract The mining in physics and biology for accelerating the hardcore algorithm to solve non-deterministic polynomial (NP) hard problems has inspired a great amount of special-purpose ma-chine models. Ising machine has become an efficient solver for various combinatorial optimization problems. As a computing accelerator, large-scale photonic spatial Ising machine have great advantages and potentials due to excellent scalability and compact system. However, current fundamental limitation of photonic spatial Ising machine is the configuration flexibility of problem implementation in the accelerator model. Arbitrary spin interaction is highly desired for solving various NP hard problems. Moreover, the absence of external magnetic field in the proposed photonic Ising machine will further narrow the freedom to map the optimization applications. In this paper, we propose a novel quadrature photonic spatial Ising machine to break through the limitation of photonic Ising accelerator by synchronous phase manipulation in two and three sections. Max-cut problem solution with graph order of 100 and density from 0.5 to 1 is experimentally demonstrated after almost 100 iterations. We derive and verify using simulation the solution for Max-cut problem with more than 1600 nodes and the system tolerance for light misalignment. Moreover, vertex cover problem, modeled as an Ising model with external magnetic field, has been successfully implemented to achieve the optimal solution. Our work suggests flexible problem solution by large-scale photonic spatial Ising machine.

•Jun 16, 2021•2 citations

Quantum computing for optical system design

Daniel Pérez Calero, Robert S. Wezeman, Stefan Baümer

SPIE Optical Design and Engineering•Apr 10, 2026•0 citations
We present a rigorous, self-contained proof that an idealised Ising Machine (IM)-defined axiomatically from the experimentally observed properties of coherent Ising machines (CIMs), quantum annealers, and memristive/optical Ising processors-satisfies every clause of the canonical definition of a non-deterministic computing device in the sense of Turing (1936), Rabin and Scott (1959), and Cook (1971). Concretely, we show that (i) The physical ground-state search performed by an N-spin Ising Machine is not a deterministic computation: the machine simultaneously and physically explores an exponential number of spin configurations, and the branch that is "selected" (the ground state) is not the output of any single deterministic trajectory. (ii) There exists a polynomial-time simulation of any non-deterministic Turing machine (NDTM) by a suitably scaled Ising Machine, and conversely, every Ising Machine computation can be simulated by an NDTM in polynomial time. Hence the Ising Machine decides exactly the class NP in polynomial physical time. (iii) Because NP is, by definition, the class of languages decidable in polynomial time on a non-deterministic machine, a scalable Ising Machine would solve every NP problem in polynomial time, rendering all cryptographic schemes whose security relies on NP-hard or presumed-intractable problems (RSA, ECC, lattice-based, subset-sum-based, code-based, etc.) insecure. The argument is structured axiomatically: we first isolate the minimal physical axioms an Ising Machine must satisfy, then construct a formal mapping to the NDTM model, and finally derive the complexity-theoretic and cryptographic consequences. We discuss the crucial role of the scalability assumption and the engineering gap that currently prevents the full realisation of the threat.
Abstract The mining in physics and biology for accelerating the hardcore algorithm to solve non-deterministic polynomial (NP) hard problems has inspired a great amount of special-purpose ma-chine models. Ising machine has become an efficient solver for various combinatorial optimization problems. As a computing accelerator, large-scale photonic spatial Ising machine have great advantages and potentials due to excellent scalability and compact system. However, current fundamental limitation of photonic spatial Ising machine is the configuration flexibility of problem implementation in the accelerator model. Arbitrary spin interaction is highly desired for solving various NP hard problems. Moreover, the absence of external magnetic field in the proposed photonic Ising machine will further narrow the freedom to map the optimization applications. In this paper, we propose a novel quadrature photonic spatial Ising machine to break through the limitation of photonic Ising accelerator by synchronous phase manipulation in two and three sections. Max-cut problem solution with graph order of 100 and density from 0.5 to 1 is experimentally demonstrated after almost 100 iterations. We derive and verify using simulation the solution for Max-cut problem with more than 1600 nodes and the system tolerance for light misalignment. Moreover, vertex cover problem, modeled as an Ising model with external magnetic field, has been successfully implemented to achieve the optimal solution. Our work suggests flexible problem solution by large-scale photonic spatial Ising machine.