19
$\begingroup$

Seeing the news about 14 entangled states today @ Innsbruck:

I haven't found a clear guide online to how many qubits we are aiming for a first practical quantum computer, e.g. Factorization, Search or re-implementing large scale computing problems?

  1. Given the relatively few algorithms we have, and the fact that algorithms don't necessarily have to map 1:1 with the size of the domain (i.e. be multi-step), can we make any reasonable guesses for the above use cases?

The Wikipedia entry for Shor's algorithm seems to state "The input and output qubit registers need ... twice as many qubits as necessary ..." so we would need 1024 qubits for common encryption in use today e.g. AES. Is this a correct understanding?

references: http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Key_size

Are more info on any quantum algorithms suitable for large scale computing problems yet? e.g. 50-100 qubits for 'useful' (1999) eigen* calculations http://prl.aps.org/abstract/PRL/v83/i24/p5162_1 - only have access to the abstract

Cheers

Improve this question
$\endgroup$
5
  • $\begingroup$ I doubt it's AES, more likely RSA ;-) Common bit length for RSA is 1024 with 2048 being more and more often default. $\endgroup$
    – BarsMonster
    Apr 6, 2011 at 8:33
  • $\begingroup$ Peter Shor is an active member of the Theoretical Computer Science (TCS) Stack Exchange site. I see this question as appropriate for both Physics and TCS, but if you don't get any response here to this question, I would consider asking to move the question to their site (after all this is also a question about computation). $\endgroup$
    – Amelio Vazquez-Reina
    Apr 6, 2011 at 12:06
  • $\begingroup$ I can't read your question without hearing Bill Cosby in my head. How did you do that? $\endgroup$
    – Jerry Asher
    Apr 7, 2011 at 23:06
  • 2
    $\begingroup$ Zalka gives a version of Shor's algorithm requiring only $\lceil 1.5\log n\rceil+2$ qubits, so 1000 qubits is a good threshold for doing useful factoring. $\endgroup$
    – Charles
    Jun 20, 2013 at 1:43
  • 1
    $\begingroup$ And Seifert says it can be done in $(1+\varepsilon)\log n$ qubits. I don't know the size of the implicit error term but this could lower the threshold to 700 or so. $\endgroup$
    – Charles
    Jun 20, 2013 at 1:51

2 Answers 2

Reset to default
7
$\begingroup$

For modeling of physical (and chemical) systems on quantum computer even 25-30 qubits would be already quite nice, see Lanyon, et al, “Towards Quantum Chemistry on a Quantum Computer”, Nature Chemistry 2, 106 - 111 (2009) (see also http://arxiv.org/abs/0905.0887 )

Really, quant-ph section in arXiv.org is standard place for papers about quantum computers, the paper from PRL you mentioned also may be found there (but seems I may post only one link).

Improve this answer
$\endgroup$
3
  • $\begingroup$ The second link is arxiv.org/abs/quant-ph/9807070 $\endgroup$
    – Alex 'qubeat'
    Apr 30, 2011 at 15:03
  • 2
    $\begingroup$ In the estimation I also used the fact, that brute-force simulation on classical supercomputers nowadays is limited to 24 qubits or so. $\endgroup$
    – Alex 'qubeat'
    May 30, 2011 at 11:58
  • $\begingroup$ all the authors expect perfect correlations. If you work on experimental datas, it seems not so clear ... $\endgroup$
    – user46925
    Jun 8, 2016 at 15:42
0
$\begingroup$

In this paper you can find a way to drastically reduce number of required qubits:

arxiv.org: Shor's algorithm with fewer (pure) qubits

Christof Zalka (Submitted on 15 Jan 2006)

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ It's appreciated if you can add a flavor of what's in the paper. $\endgroup$
    – Ali
    Aug 8, 2013 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.