We introduce a framework for combinatorial optimization using sum-constrained continuous quadratic programs solvable by QCi's Dirac-3S photonic entropy computer. This is enabled by the Motzkin-Straus theorem which provides a powerful bridge between discrete clique problems and optimization over the probability simplex. We demonstrate this framework's versatility by solving constraint satisfaction problems, providing extensive benchmarks on the DIMACS suite. The Dirac-3S platform matches or outright leads two independently implemented classical baselines on more than four-fifths of the benchmark instances, reaching the best known solution on nearly all structured graph families, even outperforming both classical solvers on several of the largest instances tested. On the other hand, well-tuned classical continuous optimizers retain an edge only on the hardest planted-clique instances. This work establishes a viable pathway for solving combinatorial optimization problems using natively analog unconventional computing platforms, while positioning entropy computing as a competitive approach for navigating non-convex landscapes and providing rigorous baselines for an emerging computational paradigm.
We introduce a framework for combinatorial optimization using sum-constrained continuous quadratic programs solvable by QCi's Dirac-3S photonic entropy computer. This is enabled by the Motzkin-Straus theorem which provides a powerful bridge between discrete clique problems and optimization over the probability simplex. We demonstrate this framework's versatility by solving constraint satisfaction problems, providing extensive benchmarks on the DIMACS suite. The Dirac-3S platform matches or outright leads two independently implemented classical baselines on more than four-fifths of the benchmark instances, reaching the best known solution on nearly all structured graph families, even outperforming both classical solvers on several of the largest instances tested. On the other hand, well-tuned classical continuous optimizers retain an edge only on the hardest planted-clique instances. This work establishes a viable pathway for solving combinatorial optimization problems using natively analog unconventional computing platforms, while positioning entropy computing as a competitive approach for navigating non-convex landscapes and providing rigorous baselines for an emerging computational paradigm.
Computational protein design (CPD) is a central problem in biotechnology, with applications in enzyme engineering and therapeutic design, but its combinatorial complexity poses a significant challenge for classical optimization methods. In this work, we formulate fixed-backbone CPD as a quadratic Hamiltonian over rotamer variables, enabling solution using Quantum Computing Inc.'s photonic entropy computing platform, Dirac-3. We evaluate solution quality by benchmarking against an exact classical cost function network (CFN) solver, which provides provably optimal baselines. On a set of standard benchmark proteins ranging from 493 to 943 variables, Dirac-3 produces best-observed solutions (over 100 samples per instance) within 0.16-2.47% of the optimal energies. These results show that the proposed formulation can identify low-energy configurations on directly solvable CPD instances, while sample-level energy distributions vary by instance. Runtime behavior is reported over the tested regime, where CFN remains faster in absolute terms, while Dirac-3 exhibits moderate growth in runtime with problem size. This study focuses on optimization performance as measured by energy relative to exact baselines under a pairwise fixed-backbone energy model. Exploratory experiments on larger instances using decomposition-based approaches are provided in the Supplementary Material. Overall, the results establish a benchmark for entropy-based optimization on CPD formulations within the directly solvable regime.
Abstract Finding better solutions to combinatorial optimization problems could have a large positive impact on many real-world application areas, such as logistics. For this reason, significant efforts have been made to design novel optimization paradigms. Here we show an early instance of such paradigm in an optical setting, the entropy computing paradigm. Specifically, we experimentally demonstrate the feasibility of entropy computing by building a hybrid photonic-electronic computer that uses optical measurement and feedback to solve non-convex optimization problems. The system functions by using temporal photonic modes to create qudits in order to encode probability amplitudes in the time-frequency degree of freedom of a photon. This scheme, when coupled with with electronic interconnects, allows us to encode an arbitrary Hamiltonian into the system and solve non-convex continuous variables and combinatorial optimization problems. We show that the proposed entropy computing paradigm can act as a scalable and versatile platform for tackling a large range of NP-hard optimization problems.
Gaussian Boson Sampling (GBS) is a quantum computational model that leverages linear optics to solve sampling problems believed to be classically intractable. Recent experimental breakthroughs have demonstrated quantum advantage using GBS, motivating its application to real-world combinatorial optimization problems.
In this work, we reformulate the graph coloring problem as an integer programming problem using the independent set formulation. This enables the use of GBS to identify cliques in the complement graph, which correspond to independent sets in the original graph. Our method is benchmarked against classical heuristics and exact algorithms on two sets of instances: Erdős-Rényi random graphs and graphs derived from a smart-charging use case. The results demonstrate that GBS can provide competitive solutions, highlighting its potential as a quantum-enhanced heuristic for graph-based optimization.
A study published on bioRxiv successfully formulated the complex combinatorial problem of fixed-backbone computational protein design as a quadratic Hamiltonian, naturally mapping it onto the hybrid photonic entropy computing platform, Dirac-3. Benchmarking results on protein instances ranging from 493 to 943 variables confirmed that the photonic solver derives high-precision solutions, reaching within 0.16–2.47% of optimal energies. By overcoming the sharp super-polynomial runtime growth of existing classical solvers and implementing near-linear polynomial scaling, it established a scalable framework capable of integrating quantum-inspired hardware into practical protein engineering pipelines. [Quantum Biology Society] Customized computational protein design is considered a core challenge in next-generation drug discovery and biotechnology. However, due to the enormous combinatorial complexity of amino acid sequence combinations, existing classical optimization methods have faced fatal computational bottlenecks. Recently, a groundbreaking study breaking through this massive computational barrier using quantum-inspired hardware based on the physics of light has been published, drawing significant attention. The paper "Entropy Quantum Computing for Fixed-Backbone Protein Design," published on the preprint repository bioRxiv, presents a pioneering demonstration of applying photon-based entropy computing to biotechnology. A joint research team led by Babak Emami from Quantum Computing Inc. (QCi) and Professor David J. Huggins from Weill Cornell Medicine spearheaded this innovative study. ■ Mapping Protein Design to a Physical Model of Light The research team newly formulated the amino acid rotamer variables of a protein with a fixed backbone into a physical energy function known as a quadratic Hamiltonian. This transformed optimization problem maps naturally onto Dirac-3, a hybrid photonic entropy computing platform. Instead of existing computers repeating complex numerical calculations via transistors, this is an innovative approach where an optical system utilizes thermodynamic entropy to guide itself toward the most stable ground energy state (the optimal solution). ■ Overwhelming Scalability Beyond Classical Limits The true value of this photonic solver was clearly revealed in benchmarking experiments on large protein instances ranging from 493 to 943 variables. While the existing classical solver (CFN-based) reached a practical operational limit with a sharp super-polynomial runtime growth beyond approximately 1,000 variables, the Dirac-3 platform firmly maintained a near-linear polynomial scaling. What is even more surprising is that while enjoying this computational speed advantage, the final derived solutions recorded a highly precise level, within 0.16–2.47% of the perfect optimal energy. ■ A Quantum Framework for Next-Generation Protein Engineering This demonstration proves the overwhelming viability that entropy-based quantum optimization can surpass the limits of existing supercomputers in highly dense sequence spaces. The framework established by the research team lays a physical foundation to seamlessly integrate quantum-inspired hardware into practical protein engineering and large-scale screening pipelines, dramatically eliminating the massive friction of conventional computational processes. In the near future, utilizing light and entropy computing, humanity may witness a revolutionary leap in designing novel enzymes and therapeutic antibodies—which do not exist in nature—in real time. https://www.biorxiv.org/content/10.64898/2026.02.20.706589v1
A range of quantum algorithms, especially those leveraging variational parameterization and circuit-based optimization, are being studied as alternatives for solving classically intractable combinatorial optimization problems (COPs). However, their applicability is limited by hardware constraints, including shallow circuit depth, limited qubit counts, and noise. To mitigate these issues, we propose a hybrid classical--quantum framework based on graph shrinking to reduce the number of variables and constraints in QUBO formulations of COPs, while preserving problem structure. Our approach introduces three key ideas: (i) constraint-aware shrinking that prevents merges that will likely violate problem-specific feasibility constraints, (ii) a verification-and-repair pipeline to correct infeasible solutions post-optimization, and (iii) adaptive strategies for recalculating correlations and controlling the graph shrinking process. We apply our approach to three standard benchmark problems: Multidimensional Knapsack (MDKP), Maximum Independent Set (MIS), and the Quadratic Assignment Problem (QAP). Empirical results show that our approach improves solution feasibility, reduces repair complexity, and enhances quantum optimization quality on hardware-limited instances. These findings demonstrate a scalable pathway for applying near-term quantum algorithms to classically challenging constrained optimization problems.
Over the past decades, the operations research community has developed numerous effective optimization algorithms, yet quantum computing is emerging as a new computational paradigm with the potential to approach optimization problems more efficiently. Grover's algorithm offers a provable speedup for combinatorial optimization, but its circuit depth places it beyond current noisy intermediate-scale quantum (NISQ) devices. A more accessible alternative is to reformulate the optimization problem as a quadratic unconstrained binary optimization (QUBO) problem and apply quantum annealing; however, practical problem instances remain out of reach for existing hardware. We introduce AtomTreeSearch, a hybrid classical-quantum algorithm that integrates a quantum subroutine natively implementable on neutral-atom quantum computers within a Monte Carlo Tree Search framework. At each expansion step, a maximal weighted independent set of candidate actions provided by the quantum processor is selected, and these collective actions are performed to obtain a child node. We benchmark our method on the Traveling Salesman Problem, with instances of up to 60 cities on random Euclidean instances and up to 100 cities on TSPLIB instances. Our hybrid algorithm generally matches or outperforms both OR-Tools and simulated annealing on these instances, and we find that the quantum subroutine produces more diverse and higher-quality branches compared to classical alternate subroutines. These results suggest that carefully scoped quantum subroutines embedded in classical search frameworks represent a promising path toward near-term quantum utility in combinatorial optimization.