3
$\begingroup$

I've seen many articles in the popular press saying that quantum computers will enable searching through huge amounts of data in an instant. But I can't figure out how the current architectures can do that at all, things like Google's Sycamore architecture don't even have storage. There is literally nothing to search except for the state space that results from the configuration of the gates (and that seems to be an RF signal that is spread out over time).

So how will quantum computers search anything, other than tuning parameters?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Qiskit and other programming languages allow to write a hybrid algorithms, i.e. combination of classical and quantum algorithm. Inputs to quantum algorithm can be pre-processed on classical computer and results produced by quantum computers can be post-processed again classically.

You are right that storage is still a problem. So far quantum RAM (qRAM) was proposed. However, it also face problems such a decoherence.

You can find a proposal of quantum RAM architecture here: Quantum random access memory

Some discussion on qRAM is on this forum here.

Overall, data can be stored classically and access via hybrid algorithms. However, in this case part of quantum speed-up is lost.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Thanks. If data is stored classically, then any data-bound algorithm will not see significant quantum speedup, I think. Even today's classical computers are mostly memory-bound. $\endgroup$
    – vy32
    Jan 24, 2020 at 23:30
  • $\begingroup$ @vy32: Yes, you are right. Pre- and post-processing can reduce the speed-up. Generally, quantum computers are not supposed to replace classical ones in all cases. They will help us in specific tasks despite the fact they are universal. If my answer is satisfactory for you, would you please accept it? $\endgroup$
    – Martin Vesely
    Jan 26, 2020 at 7:31
  • 1
    $\begingroup$ Sure. I was previously criticized here for accepting an answer too fast. $\endgroup$
    – vy32
    Jan 26, 2020 at 12:04
  • $\begingroup$ "Overall, data can be stored classically and access via hybrid algorithms" I mean, every single "quantum algorithm" is a "hybrid algorithm", even though we often only discuss explicitly the quantum part of it. You need classical inputs and outputs to talk meaningfully of an algorithm doing something. This doesn't have much to do with the question of how QCs can access classical datasets (the qRAM part of the answer does though) $\endgroup$
    – glS ♦
    Jan 27, 2020 at 14:04
  • $\begingroup$ @gIS: You are right that input and output are classical for all algorithms. But when we will have qRAMs we will simply copy classical data there, process them on quantum computer without any interaction with classical computer and then we will read the output. Input and output are the only classical part and all processing is done on quantum computer. But now, to process big amount of data, quantum computer has to communicate with classical storage more often because the quantum computer does not have a memory, only few qubits in qunatum processor itself. $\endgroup$
    – Martin Vesely
    Jan 27, 2020 at 14:20
2
$\begingroup$

Typically, quantum search algorithm searches through a very large solution spaces that can represented by logarithmic scale of data, not directly over huge amount of data. An example is travelling salesman problem where the input data are the distances between cities, but each solution is a path and the space to be searched is exponential in terms the number of cities.

Nielsen and Chuang’s book suggested two approaches to search really unstructured data directly, by using a quantum memory, or by quantum access to classical memory.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ when talking about "quantum memories" people usually refer to the problem of storing quantum states for prolonged amounts of times (whatever that means in a given setup). This doesn't have much to do the question at hand, which is about how classical data can be loaded/encoded as a quantum state in the first place. $\endgroup$
    – glS ♦
    Jan 27, 2020 at 14:06
  • $\begingroup$ I don't see how reducing a large amount of data to a logarithmic scale of data helps. I also don't see how this could be done for, say, web pages. $\endgroup$
    – vy32
    Feb 4, 2020 at 2:25

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.