44

Yes, a quantum computer could be simulated by a Turing machine, though this shouldn't be taken to imply that real-world quantum computers couldn't enjoy quantum advantage, i.e. a significant implementation advantage over real-world classical computers. As a rule-of-thumb, if a human could manually describe or imagine how something ought to operate, that ...


26

Yes, it can do so in a rather trivial way: Use only reversible classical logical gates to simulate computations using boolean logic (for instance, using TOFFOLI to simulate NAND gates), use only the standard basis states $\lvert 0\rangle$ and $\lvert 1\rangle$ as input, and only perform standard basis state measurements at the output. In this way you can ...


15

One way of writing quantum programs is with QISKit. This can be used to run the programs on IBM's devices. The QISKit website suggests the following code snippet to get you going, which is an entangled circuit as you want. It is also the same process as in the answer by datell. I'll comment on it line-by-line. # import and initialize the method used to ...


15

There are plenty of different variants, particularly with regards to the conditions on the Hamiltonian. It's a bit of a game, for example, to try and find the simplest possible class of Hamiltonians for which simulation is still BQP-complete. The statement will roughly be along the lines of: let $|\psi\rangle$ be a (normalised) product state, $H$ be a ...


14

Suppose that you have a quantum algorithm with $2^{60}$ possible inputs. Suppose also that it would take 1 nanosecond to run this on a supercomputer (which is unrealistically optimistic!). The total time required to run through all possible inputs would be 36.5 years. Clearly it would be much better to just run the instance that you care about, and get the ...


13

Assuming you are considering a gate-based quantum computer, the most easy way to produce an entagled state is to produce one of the Bell states. The following circuit shows the Bell state $\left| \Phi^+ \right>$. By examining $\left| \psi_0 \right>$, $\left| \psi_1 \right>$ and $\left| \psi_2 \right>$ we can determine the entagled state after ...


12

First we should take a step back. Is there any machine learning done a quantum computer that cannot be efficiently simulated on a classical computer? The answer currently (2020) is no. In this respect quantum machine learning (which has many variants) is at the fundamental research phase. None of this is at a stage where it is at all considered something ...


11

A conventional Hamiltonian is Hermitian. Hence, if it contains a non-Hermitian term, it must either also contain its Hermitian conjuagte as another term, or have 0 weight. In this particular case, since $Z\otimes X\otimes Y$ is Hermitian itself, the coefficient would have to be 0. So, if you're talking about conventional Hamiltonians, you've probably made a ...


11

To my mind, this theorem is not very well stated in this form, if taken out of context. Where it says "phase gates", this may be misleading. It means specifically just $S=\sqrt{Z}$ and not what I think of as a phase gate, which can have an arbitrary phase (but they have very specifically introduced their terminology about 3 pages earlier). This is a key ...


10

That depends on your definitions of "commercial" and of "quantum computer". The company D-Wave Systems has been offering what they call quantum computers commercially since 2011. Many things seem to point towards those being adiabatic quantum computers (though people disagree on this). That doesn't quite fit the kind of quantum computers that are becoming ...


10

I guess that he's right enough for the moment; quantum mechanics is part of our best theory of the universe, which by definition means that we think the universe works like that. It's pretty circular though. When we have some model of the universe, what that literally means is that we think that the universe is operating according to that model. Currently ...


10

Yes, it is possible to obtain this information, but only for troubleshooting purposes, not for using it in the code. Dump functions dump the status of the target machine into a file or to the console output. If the program is executed on the full-state simulator, this status will include the wave function of the whole system (for DumpMachine) or of the ...


10

There are two questions here. The first asks how you might actually implement this in code, and the second asks what's the point if you know which oracle you're passing in. Implementation Probably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant....


10

Apart from the formal result about #P-hardness, there's something worth touching on, about the nature of strong simulation itself. I'll comment first on strong simulation, and then specifically on the quantum case. 1. Strong simulation even of classical randomised computation is hard Strong simulation is a very powerful concept — not only in the fact ...


9

$\newcommand{\ket}[1]{\left|#1\right>}$I'm not sure using sparsity is a good approach here: even single-qubit gates could easily turn a sparse state into a dense one. But you can use the stabilizer formalism if you only use Clifford gates. Here is a short recap (notation): The single-qubit Pauli group is $G_1=\langle X, Y, Z\rangle$, i.e. all possible ...


9

To simulate the collapse of the wave function you'd need a source of randomness. So you'd need a probabilistic Turing machine.


9

I believe what you're after is NIST's Quantum Zoo, a comprehensive catalog of quantum algorithms maintained by Stephen Jordan. Its sections include: Algebraic and Number Theoretic Algorithms (14 items) Oracular Algorithms (34 items) Approximation and Simulation Algorithms (12 items) and for each algorithm it includes its speedup, a description and relevant ...


9

One way order to perform Z rotations by arbitrary angles is to approximate them with a sequence of Hadamard and T gates. If you need the approximation to have maximum error $\epsilon$, there are known constructions that do this using roughly $3 \lg \frac{1}{\epsilon}$ T gates. See "Optimal ancilla-free Clifford+T approximation of z-rotations" by Ross et al. ...


8

There are many possible ways to compactly represent a state, the usefulness of which strongly depend on the context. First of all, it is important to notice that it is not possible to have a procedure that can map any state into a more efficient representation of the same state (for the same reason why it is obviously not possible to faithfully compress any ...


7

Taking your comment to Kiro to its logical conclusion, the answer is 'yes'. The basic idea is to decompose the T gate 'magic' state $\tfrac{1}{\sqrt 2}\bigl(\lvert 0 \rangle + \mathrm{e}^{i \pi / 4} \lvert 1 \rangle \bigr)$ as a linear combination of stabiliser states. (If you do this for several magic states, this produces an exponentially large linear ...


7

Virtual reality in a classical computer is just a fancy front-end on top of a classical simulation. A classical computer can simulate all of the quantum physics happening inside a quantum computer, including all the phenomena referred to in the question, but only for a limited number of qubits. A 45-qubit circuit was simulated using 0.5PB of RAM in 2017. ...


7

It depends on the Hamiltonian. There are three particular questions whose answers might influence your choice of strategy: Does the Hamiltonian have any particular structure or symmetry? How quickly does the Hamiltonian change in time? What do you know about the initial state in relation to the initial Hamiltonian? Obviously, if the Hamiltonian has any ...


7

Quantum simulators don't rely on quantum-mechanical effects in the physical chips; instead they simulate certain aspects of quantum state and operations on it using only classical compute. Universal simulators simulate full quantum state of the system, performing linear algebra transformations on it. They support universal set of quantum operations, but the ...


7

There is a distinction between what you use to write a program (the SDK), and what you use to run it (the backend). The SDK can be either a graphical interface, like the IBM Q Experience or the CAS-Alibaba Quantum Computing Laboratory. It could also be a way of writing programs, like Q#, QISKit, Forest, Circ, ProjectQ, etc. The backend can either be a ...


7

There isn't much of a difference. If you read the labels, the values are roughly the same but for some reason are presented in a different order. Any differences for a given value are due to noise and decoherence.


7

TL;DR: Hamiltonian simulation does not just mean "exponentiating $H$". It means finding a quantum circuit $U$ that approximates the matrix exponentiation $e^{-iHt}$. More importantly, the size of the Hamiltonian matrix $H$ isn't the key concern here. The gate complexity (or query complexity, in case the Hamiltonian is described as an oracle) of matrix ...


7

This is incorrect. The QASM simulator by default has no noise. The fluctuations in its results are a result of finite sampling of the output statevector. Thus, the QASM simulator is equivalent to running a quantum circuit on an ideal quantum computer. To add noise you can follow the example here: https://www.qiskit.org/aer


6

Let me first answer the general question how to get a reasonably tight Lieb-Robinson (LR) speed when you are facing a generic locally interacting lattice model, and then I'll come back to the 1D XY model in your question, which is very special to be exactly solvable. General Method The method to obtain the tightest bound to date (for a generic short-range ...


6

To complete what others have said: as far as we know a (classical) Turing machine cannot truly simulate quantum correlations. This is explicitly claimed in section Properties of the universal quantum computer by the seminal paper by David Deutsch Quantum theory, the Church-Turing principle and the universal quantum computer (Proceedings of the Royal Society ...


6

A separate note on using simulators for this (as opposed to using an actual quantum computer). Simulators, like the one that ships with Q#, are built to simulate quantum mechanical theories as we understand them now. This means that any experiment you run on a simulator will behave exactly as the theory says (well, unless the simulator has a bug in the code)...


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