Tag Info

24

Regarding your first question, you are essentially asking about the validity of a position taken by David Deutsch - a founder of quantum computing! For example, in his book 'The Fabric of Reality', Deutsch states: When Shor’s algorithm has factorized a number, using $10^{500}$ or so times the computational resources that can be seen to be present, where ...

15

Question 1 This description lies somewhere between the two extremes of a theory and mysticism, depending on how amiable one is to the concept. David Deutsch is vocal proponent of the former, Lee Smolin of the latter (he categorizes it as "Mystical Realism"). The general idea was initiated by one of John Wheeler's PhD students, Hugh Everett III, in ...

8

In the many worlds interpretation (MWI) reality consists of a structure called the multiverse that looks like a collection of slightly interacting parallel universes in some circumstances: Deutsch, David. "The structure of the multiverse." Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 458.2028 (2002):...

6

To answer your first question, the quantum oracles are defined by their effect on the basis states $|0\rangle$ and $|1\rangle$, and if the oracle has to be computed on a superposition of basis states, its effects are expressed using the fact that the oracle is a linear transformation. This means that you never compute $f(|+\rangle)$; instead, to compute the ...

6

The point is that free parallel computation or cloning of your existence is a wholesale misinterpretation of the concept of quantum superposition. Quantum states are analogous to probability distributions. If you might wash the dishes or you might wash the floor and you flip a coin to decide which one, then no one takes that to mean that you will wash ...

5

As I suggest in the comments, I don't think that it is going to help you to understand quantum computation in terms of parallelism. To illustrate why, I will describe a simple two-qubit computation, in which — if you were absolutely adamant — you could claim there is computation happening in parallel; but which I would suggest does not in any ...

4

Intuition is just that - intuition. It's is not an absolute of "this is how it works", but rather something that helps you get some sort of intuition about what's happening. In that sense, there is no "right" or "wrong". It's what helps you. Different people understand things in different ways. You just have to be clear that every intuitive explanation has ...

4

Recall that the operations that one applies on a quantum state are actually unitary matrices. In particular, these operations are reversible, since these matrices can be inverted. Now, let us consider the map: $$|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle$$ If you were to write the matrix corresponding to this mapping, you would end up with a ...

3

We are not at the point where quantum computers are outperforming classical computers in any practical way so certainly not now. As for the future, there already exist numerous algorithms which have been shown to theoretically outperform classical computers so once the hardware catches up we should be in a good place to take advantage of it. Regarding the ...

3

My reason for asking the question is that Deutsch seems to be implying that quantum parallelism is real, and that it can be used for significant speedup, but my understanding is that quantum parallelism, in this sense, does not exist. This is an interpretational issue. If you are an Everettian, then quantum parallelism is real and this is the source of the ...

3

The statement is meant to get in front of any misconceptions, for example by the science press, about how quantum computers operate. It's not a "no-go" in the sense of a theorem, nor do I believe many researchers have spent much time considering a possible algorithm that "simply tries all possible solutions at once." I believe it's meant to say that ...

3

So, this isn't a question with a single "correct" physical answer. In general, though I would say that the parallel nature of quantum algorithms is dramatically overplayed, especially in older literature and a lot of the popular science press. Remember that whatever parallelism is happening as your quantum state evolves, once you measure you're going to ...

2

Generically, given any controlled-$U$, you cannot go backwards and work out the function $f(x)$, because it may not exist. For example, controlled-Hadamard takes a basis state and returns a superposition of basis states rather than a single basis state output. So there's no single $f(x)$ value to identify. If it happens to be the case that for all inputs of ...

2

For $cX$,$cY$ and $cZ$ first. Let $U_Y$ be the 1 qubit unitary such that $U_Y^\dagger X U_Y = Y$ and similarly for $Z$. This can be done because they all diagonalize to the same thing $Z$, so you can find that $U$ as an exercise. Suppose you did $U_Y$ on the target qubit, then a CNOT and then a $U_Y^\dagger$ on the second qubit. If the initial state is of ...

2

I feel you, I hate when the somebody explains a qubit using the "0 and 1 at the same time" phrase. I prefer the following analogy: A qubit is like a coin being tossed. It is not heads and tails at the same time. It's in a probabilistic position. While flying, the state of the coin is not determined yet and it can be described as a probability. In ...

2

If you could completely separate a computation between two different processors, then, in fact, one processor would be enough, and you could run one computation after the other. What you can do is try to rearrange a computation that minimises the number of two-qubit gates acting between two distinct blocks of qubits. Those two-qubit gates probably then need ...

2

am I sure that the compiler will always be able to decompose this big gate into a succession of smaller, allowed gates, without breaking the complexity No, you're not. This is the whole problem with algorithms, be they classical or quantum. However, in the specific case you're talking about, there is a nice implementation. Imagine that you want to apply ...

2

do we need to come up with completely different quantum-based solutions for such problems, or is there a way to 'interpret' existing algorithms to the quantum domain and still expect some speedup? Generally speaking yes, you need to come up with different algorithms. You cannot simply take a classical algorithm and "quantize it" in a straightforward way. ...

2

$U_f$ is defined as $U_f: |x\rangle|y\rangle \rightarrow |x\rangle|y\oplus f(x)\rangle$. Now, let's write the product state of the complete system of two qubits before applying $U_f$. We can do this with tensor products as follows: $$\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |0\rangle = \frac{1}{\sqrt{2}}(|0\rangle\otimes|0\rangle + |1\rangle\otimes|... 2 If I understand you correctly, your goal is: To choose some quantum algorithm (your question is: which algorithm would be good?) Instead of running the quantum algorithm on a real quantum computer, you want to run a simulation of a quantum computer on a classical computer to simulate the execution of the quantum algorithm. You want to optimize your ... 1 Each qiskit.QuantumCircuit has a name attribute that is also accessible through each qiskit.result.Result. So, you can do the following to match the circuits to the measurement counts after running in parallel: for circuit in qcircuits: print(circuit.name) result_dict = jobs.result().to_dict()["results"] result_counts = jobs.result().... 1 Where does that single evaluation of f(x) actually occur? Is it in the construction of U_f? U_f is an implementation of f in quantum gates. The evaluation of f occurs in the course of applying the gates making up U_f to the qubits. What is U_f in this case? I realize it depends on f, but how can we build it using at most one evaluation of ... 1 Any quantum system can be in so-called superposition state. Imagine that the system's possible states are s_1, s_2...s_n. There is also an amplitude for each state a_1, a_2...a_n (a probability that the system is in state s_i is p_i =|a_i|^2). Then the system can be in superposition$$ \sum_{i=1}^n s_i a_i.  The system remains in this "...

1

The reason that a quantum computer is faster in same tasks is given by different computational paradigm based on quantum mechanics laws. They mainly exploit superposition (i.e. state of qubit is linear combination of zero state and one state) and quantum entanglement (i.e. two or more qubits are connected and they behave as one system, or in other words ...

1

'Quantum parallelism' is a common misconception - sure, the quantum computer does compute in a 'parallel' fashion, but really the power of quantum computing emerges from constructive / destructive interference. If you wanted, you could absolutely make a quantum computer behave in a classical format: constantly measure the qubits and correct if necessary. ...

Only top voted, non community-wiki answers of a minimum length are eligible