Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols
Abstract Photonic graph states are important for measurement- and fusion-based quantum computing, quantum networks, and sensing. They can in principle be generated deterministically by using emitters to create the requisite entanglement. Finding ways to minimize the number of entangling gates betwee...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-07-01
|
| Series: | npj Quantum Information |
| Online Access: | https://doi.org/10.1038/s41534-025-01056-3 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849238378454712320 |
|---|---|
| author | Evangelia Takou Edwin Barnes Sophia E. Economou |
| author_facet | Evangelia Takou Edwin Barnes Sophia E. Economou |
| author_sort | Evangelia Takou |
| collection | DOAJ |
| description | Abstract Photonic graph states are important for measurement- and fusion-based quantum computing, quantum networks, and sensing. They can in principle be generated deterministically by using emitters to create the requisite entanglement. Finding ways to minimize the number of entangling gates between emitters and understanding the overall optimization complexity of such protocols is crucial for practical implementations. Here, we address these issues using graph theory concepts. We develop optimizers that minimize the number of entangling gates, reducing them by up to 75% compared to naive schemes for moderately sized random graphs. While the complexity of optimizing emitter-emitter CNOT counts is likely NP-hard, we are able to develop heuristics based on strong connections between graph transformations and the optimization of stabilizer circuits. These patterns allow us to process large graphs and still achieve a reduction of up to 66% in emitter CNOTs, without relying on subtle metrics such as edge density. We find the optimal emission orderings and circuits to prepare unencoded and encoded repeater graph states of any size, achieving global minimization of emitter and CNOT resources despite the average NP-hardness of both optimization problems. We further study the locally equivalent orbit of graphs. Although enumerating orbits is #P complete for arbitrary graphs, we analytically calculate the size of the orbit of repeater graphs and find a procedure to generate the orbit for any repeater size. Finally, we inspect the entangling gate cost of preparing any graph from a given orbit and show that we can achieve the same optimal CNOT count across the orbit. |
| format | Article |
| id | doaj-art-839cb16bcf244e938cfed7eeaab9002d |
| institution | Kabale University |
| issn | 2056-6387 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | npj Quantum Information |
| spelling | doaj-art-839cb16bcf244e938cfed7eeaab9002d2025-08-20T04:01:40ZengNature Portfolionpj Quantum Information2056-63872025-07-0111111710.1038/s41534-025-01056-3Optimization complexity and resource minimization of emitter-based photonic graph state generation protocolsEvangelia Takou0Edwin Barnes1Sophia E. Economou2Department of Physics, Virginia TechDepartment of Physics, Virginia TechDepartment of Physics, Virginia TechAbstract Photonic graph states are important for measurement- and fusion-based quantum computing, quantum networks, and sensing. They can in principle be generated deterministically by using emitters to create the requisite entanglement. Finding ways to minimize the number of entangling gates between emitters and understanding the overall optimization complexity of such protocols is crucial for practical implementations. Here, we address these issues using graph theory concepts. We develop optimizers that minimize the number of entangling gates, reducing them by up to 75% compared to naive schemes for moderately sized random graphs. While the complexity of optimizing emitter-emitter CNOT counts is likely NP-hard, we are able to develop heuristics based on strong connections between graph transformations and the optimization of stabilizer circuits. These patterns allow us to process large graphs and still achieve a reduction of up to 66% in emitter CNOTs, without relying on subtle metrics such as edge density. We find the optimal emission orderings and circuits to prepare unencoded and encoded repeater graph states of any size, achieving global minimization of emitter and CNOT resources despite the average NP-hardness of both optimization problems. We further study the locally equivalent orbit of graphs. Although enumerating orbits is #P complete for arbitrary graphs, we analytically calculate the size of the orbit of repeater graphs and find a procedure to generate the orbit for any repeater size. Finally, we inspect the entangling gate cost of preparing any graph from a given orbit and show that we can achieve the same optimal CNOT count across the orbit.https://doi.org/10.1038/s41534-025-01056-3 |
| spellingShingle | Evangelia Takou Edwin Barnes Sophia E. Economou Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols npj Quantum Information |
| title | Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols |
| title_full | Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols |
| title_fullStr | Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols |
| title_full_unstemmed | Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols |
| title_short | Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols |
| title_sort | optimization complexity and resource minimization of emitter based photonic graph state generation protocols |
| url | https://doi.org/10.1038/s41534-025-01056-3 |
| work_keys_str_mv | AT evangeliatakou optimizationcomplexityandresourceminimizationofemitterbasedphotonicgraphstategenerationprotocols AT edwinbarnes optimizationcomplexityandresourceminimizationofemitterbasedphotonicgraphstategenerationprotocols AT sophiaeeconomou optimizationcomplexityandresourceminimizationofemitterbasedphotonicgraphstategenerationprotocols |