We introduce a local concept of speed-up applicable to intermediate stages of a quantum algorithm. We use it to analyse the complementary roles played by quantum parallel computation and quantum measurement in yielding the speed-up. A severe conflict between there being a speed-up and the many worlds interpretation is highlighted.
The aim of this thesis is to investigate the nature of quantum computation and the question of the quantum speed-up over classical computation by comparing two different quantum computational frameworks, the traditional quantum circuit model and the cluster-state quantum computer. After an introductory survey of the theoretical and epistemological questions concerning quantum computation, the first part of this thesis provides a presentation of cluster-state computation suitable for a philosophical audience. In spite of the computational equivalence between the two frameworks, their differences can be considered as structural. Entanglement is shown to play a fundamental role in both quantum circuits and cluster-state computers; this supports, from a new perspective, the argument that entanglement can reasonably explain the quantum speed-up over classical computation. However, quantum circuits and cluster-state computers diverge with regard to one of the explanations of quantum computation that actually accords a central role to entanglement, i.e. the Everett interpretation. It is argued that, while cluster-state quantum computation does not show an Everettian failure in accounting for the computational processes, it threatens that interpretation of being not-explanatory. This analysis presented here should be integrated in a more general work in order to include also further frameworks of quantum computation, e.g. topological quantum computation. However, what is revealed by this work is that the speed-up question does not capture all that is at stake: both quantum circuits and cluster-state computers achieve the speed-up, but the challenges that they posit go besides that specific question. Then, the existence of alternative equivalent quantum computational models suggests that the ultimate question should be moved from the speed-up to a sort of “representation theorem” for quantum computation, to be meant as the general goal of identifying the physical features underlying these alternative frameworks that allow for labelling those frameworks as “quantum computation”.
Abstract | Quantum computers are believed to surpass their classical counterparts in speed-up and efficiency. However, the origin of this speed-up in quantum algorithms is not yet fully understood. There are indications that entanglement plays an important role in quantum computation. Quantum algorithms that do not involve entanglement appear to require an exponential amount of resources and may be efficiently simulated on a classical computer. Here we discuss the role of entanglement in quantum computation. As an illustration, we consider Grover’s algorithm and how entanglement arises in this case. We will show that even though entanglement is present throughout the computation, the change of entanglement per iteration is exponentially small for large databases. 1
Quantum computation is a novel way of information processing that allows, for certain classes of problems, exponential speedups over classical computation. Various models of quantum computation exist, such as the adiabatic, circuit, and measurement-based models. They have been proven equivalent in their computational power, but operate very differently. As such, they may be suitable for realization in different physical systems, and also offer different perspectives on open questions such as the precise origin of the quantum speedup. Here, we give an introduction to the one-way quantum computer, a scheme of measurement-based quantum computation (MBQC). In this model, the computation is driven by local measurements on a carefully chosen, highly entangled state. We discuss various aspects of this computational scheme, such as the role of entanglement and quantum correlations. We also give examples for ground states of simple Hamiltonians that enable universal quantum computation by local measurements.
Origin of the speed‐up in quantum algorithms is not yet fully understood. But there are indications that entanglement does play an important role in quantum computation. Algorithms that do not involve entanglement can be efficiently simulated on a classical computer. Here I make a simple observation. I show that infinitesimal change in multi‐particle pure product state always gives rise to an entangled state. During quantum computation even though at each time instant the state is not entangled, it does pass through entangled states at infinitesimal time steps. This applies to multi‐particle pure, pseudo‐pure and general mixed states as well. This suggests that even though unitary operators do not produce any entanglement, quantum entanglement guides the process of quantum computation.
For any quantum algorithm operating on pure states, we prove that the presence of multi‐partite entanglement, with a number of parties that increases unboundedly with input size, is necessary if the quantum algorithm is to offer an exponential speed‐up over classical computation. Furthermore, we prove that the algorithm can be efficiently simulated classically to within a prescribed tolerance η even if a suitably small amount of global entanglement is present. We explicitly identify the occurrence of increasing multi‐partite entanglement in Shor's algorithm. Our results do not apply to quantum algorithms operating on mixed states in general and we discuss the suggestion that an exponential computational speed‐up might be possible with mixed states in the total absence of entanglement. Finally, despite the essential role of entanglement for pure‐state algorithms, we argue that it is nevertheless misleading to view entanglement as a key resource for quantum‐computational power.