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

arXiv:quant-ph/0510233

Quantum Measurements for Graph Isomorphism Require Entanglement: Tight Results on Multiregister Fourier Sampling (Withdrawn)

Cristopher Moore, Alexander C. Russell

Published Oct 31, 2005• 1 citation
arXivHTMLPDF

Abstract

This article has been withdrawn by the authors.
DOI
10.48550/arxiv.quant-ph/0510233

Related papers

Detection of fidelity and multiparticle entanglement for arbitrary graph states

Yashuai Han, Duan, L. -M.

withdrawn by the authors because of an error.

arXiv:0708.3119•Aug 23, 2007•0 citations

Entanglement For Ideal Quantum Ensembles

Yu. M. Suhov, T. Voice

This paper has been withdrawn by the authors, due to the discovery of paper 0201028 which predates it and contains most of it's results.

arXiv:quant-ph/0211198•Nov 29, 2002•0 citations

Withdrawn: Quantum Communication Under Memory and Entanglement Constraints

Michael Aaron Cody

This preprint has been withdrawn at the request of the author due to fundamental structural problems that cannot be resolved by updating the manuscript.

•Oct 14, 2025•0 citations

Withdrawn: Quantum Communication Under Memory and Entanglement Constraints

Michael Aaron Cody

This preprint has been withdrawn at the request of the author due to fundamental structural problems that cannot be resolved by updating the manuscript.

•Oct 23, 2025•0 citations

Graph identification by quantum walks

Jingbo B. Wang, B. L. Douglas

This paper has been withdrawn by the authors; replaced by arXiv:0705.2531v2 [quant-ph].

arXiv:quant-ph/0701033•Jan 8, 2007•1 citation

Tight Results on Multiregister Fourier Sampling: Quantum Measurements for Graph Isomorphism Require Entanglement

Cristopher Moore, Alexander C. Russell

We establish a general method for proving bounds on the information that can be extracted via arbitrary entangled measurements on tensor products of hidden subgroup coset states. When applied to the symmetric group, the method yields an Omega(n log n) lower bound on the number of coset states over which we must perform an entangled measurement in order to obtain non-negligible information about a hidden involution. These results are tight to within a multiplicative constant and apply, in particular, to the case relevant for the Graph Isomorphism problem. Part of our proof was obtained after learning from Hallgren, Roetteler, and Sen that they had obtained similar results.

arXiv:quant-ph/0511149•Nov 15, 2005•4 citations
We establish a general method for proving bounds on the information that can be extracted via arbitrary entangled measurements on tensor products of hidden subgroup coset states. When applied to the symmetric group, the method yields an Omega(n log n) lower bound on the number of coset states over which we must perform an entangled measurement in order to obtain non-negligible information about a hidden involution. These results are tight to within a multiplicative constant and apply, in particular, to the case relevant for the Graph Isomorphism problem. Part of our proof was obtained after learning from Hallgren, Roetteler, and Sen that they had obtained similar results.