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

Bulletin of the American Physical Society

Systematic and Deterministic Graph-Minor Embedding of Cartesian Products of Complete Graphs

Arman Zaribafiyan, D. J. J. Marchand, Seyed Saeed Changiz Rezaei

Published Mar 15, 2016• 1 citation
OpenAlex

Related papers

Systematic and deterministic graph minor embedding for Cartesian products of graphs

Arman Zaribafiyan, D. J. J. Marchand, Seyed Saeed Changiz Rezaei

arXiv:1602.04274•Quantum Information Processing•Apr 10, 2017•41 citations

Hard combinatorial problems and minor embeddings on lattice graphs

Andrew Lucas

arXiv:1812.01789•Quantum Information Processing•May 16, 2019•24 citations

Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design

Vicky Choi

arXiv:1001.3116•Quantum Information Processing•Oct 13, 2010•297 citations

Optimal Embedding of Complete Graphs intoBroken Chimera Graphs

Elisabeth Lobe, Lukas Schürmann, Tobias Stollenwerk

•Jun 24, 2019•0 citations

Entanglement from Expansion: High Rank-Width in Deterministic Graphs

Tristan Cam, Cyril Gavoille, Yvan Le Borgne +1 more

Entanglement in quantum graph states is intrinsically linked to rank-width, a graph complexity measure introduced by Oum and Seymour. In this work, we enable the preparation of maximally entangled deterministic graph states in constant depth by developing a general method to derive lower bounds on the rank-width of regular graphs from their edge expansion. By bridging edge-isoperimetric inequalities with the strong chromatic index and Jelínek's approach for lower bounding cut-rank, we systematically establish lower bounds for the rank-width of Cartesian products, including hypercubes, Hamming graphs, and grids. Extending this framework via Boolean function analysis, using a generalization of the Kahn-Kalai-Linial's Theorem, we strengthen the bounds for all Cartesian products by a non-trivial logarithmic factor. These methods result in the discovery of deterministic families of graphs on $n$ vertices with a provably maximum rank-width $Θ(n)$. Our results fill the previous gap in the literature for deterministic graph families of rank-width greater than $Θ(\sqrt{n})$.

arXiv:2606.07110•Jun 5, 2026•0 citations

Optimised Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph

Salvatore Sinno, Thomas Groß, Nicholas Chancellor +2 more

Minor embedding is essential for mapping largescale combinatorial problems onto quantum annealers, particularly in quantum machine learning and optimization. This work presents an optimized, universal minor-embedding framework that efficiently accommodates complete bipartite graphs onto the hardware topology of quantum annealers. By leveraging the inherent topographical periodicity of the physical quantum adiabatic annealer processor, our method systematically reduces qubit chain lengths, resulting in enhanced stability, computational efficiency, and scalability of quantum annealing. We benchmark our embedding framework against Minorminer, the default heuristic embedding algorithm, for the Pegasus topology, demonstrating that our approach significantly improves embedding quality. Our empirical results show a 99.98% reduction in embedding time for a 120 x 120 complete bipartite graphs. Additionally, our method eliminates long qubit chains, which primarily cause decoherence and computational errors in quantum annealing. These findings advance the scalability of quantum embeddings, particularly for quantum generative models, anomaly detection, and large-scale optimization tasks. Our results establish a foundation for integrating efficient quantum-classical hybrid solutions, paving the way for practical applications in quantum-enhanced machine learning and optimization.

arXiv:2504.21112•IEEE International Conference on Quantum Artificial Intelligence (QAI)•Nov 2, 2025•1 citation
Entanglement in quantum graph states is intrinsically linked to rank-width, a graph complexity measure introduced by Oum and Seymour. In this work, we enable the preparation of maximally entangled deterministic graph states in constant depth by developing a general method to derive lower bounds on the rank-width of regular graphs from their edge expansion. By bridging edge-isoperimetric inequalities with the strong chromatic index and Jelínek's approach for lower bounding cut-rank, we systematically establish lower bounds for the rank-width of Cartesian products, including hypercubes, Hamming graphs, and grids. Extending this framework via Boolean function analysis, using a generalization of the Kahn-Kalai-Linial's Theorem, we strengthen the bounds for all Cartesian products by a non-trivial logarithmic factor. These methods result in the discovery of deterministic families of graphs on nnn vertices with a provably maximum rank-width Θ(n)Θ(n)Θ(n). Our results fill the previous gap in the literature for deterministic graph families of rank-width greater than Θ(n)Θ(\sqrt{n})Θ(n​).
Minor embedding is essential for mapping largescale combinatorial problems onto quantum annealers, particularly in quantum machine learning and optimization. This work presents an optimized, universal minor-embedding framework that efficiently accommodates complete bipartite graphs onto the hardware topology of quantum annealers. By leveraging the inherent topographical periodicity of the physical quantum adiabatic annealer processor, our method systematically reduces qubit chain lengths, resulting in enhanced stability, computational efficiency, and scalability of quantum annealing. We benchmark our embedding framework against Minorminer, the default heuristic embedding algorithm, for the Pegasus topology, demonstrating that our approach significantly improves embedding quality. Our empirical results show a 99.98% reduction in embedding time for a 120 x 120 complete bipartite graphs. Additionally, our method eliminates long qubit chains, which primarily cause decoherence and computational errors in quantum annealing. These findings advance the scalability of quantum embeddings, particularly for quantum generative models, anomaly detection, and large-scale optimization tasks. Our results establish a foundation for integrating efficient quantum-classical hybrid solutions, paving the way for practical applications in quantum-enhanced machine learning and optimization.