On Shor's Factoring Algorithm with More Registers and the Problem to Certify Quantum Computers

Zhengjun Cao; Zhenfu Cao

Paper 2014/721

On Shor's Factoring Algorithm with More Registers and the Problem to Certify Quantum Computers

Zhengjun Cao and Zhenfu Cao

Abstract

Shor's factoring algorithm uses two quantum registers. By introducing more registers we show that the measured numbers in these registers which are of the same pre-measurement state, should be equal if the original Shor's complexity argument is sound. This contradicts the argument that the second register has $r$ possible measured values. There is an anonymous comment which argues that the states in these registers are entangled. If so, the entanglement involving many quantum registers can not be interpreted by the mechanism of EPR pairs and the like. In view of this peculiar entanglement has not yet been mentioned and investigated, we think the claim that the Shor's algorithm runs in polynomial time needs more physical verifications. We also discuss the problem to certify quantum computers.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Contact author(s): caozhj @ shu edu cn
History: 2014-09-16: received
Short URL: https://ia.cr/2014/721
License: CC BY

BibTeX

@misc{cryptoeprint:2014/721,
      author = {Zhengjun Cao and Zhenfu Cao},
      title = {On Shor's Factoring Algorithm with More Registers and the Problem to Certify Quantum Computers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/721},
      year = {2014},
      url = {https://eprint.iacr.org/2014/721}
}