43

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 ...


24

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

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 ...


14

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 ...


14

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 ...


11

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 ...


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 ...


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

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. ...


9

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 ...


9

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 ...


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 ...


8

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 ...


8

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....


8

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 ...


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

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


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 ...


6

tl;dr- Quantum computers can't really help us to simulate the whole universe as the universe is likely vastly more complex than even quantum mechanics can capture, plus we can't even begin to guess how big it is or many other basic fundamental features. In short, simulating the whole universe is beyond sci-fi. We can't really simulate the entire universe, ...


6

The first part of your question seems like a duplicate of an existing QC SE post: Are there emulators for quantum computers?. I'm not completely sure what you mean by building a quantum computer from scratch inside simulations. However, yes, you can make software simulations of a quantum computer using your average laptop/desktop. The exact "limit" will ...


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)...


6

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.


5

In the computational $\left(Z\right)$ basis, the parity of a (classical) bit string is $0$ if the number of $1$s in the string is even (i.e. 'even parity'), or $1$ if the number of $1$s in the string is odd (i.e. 'odd parity'). The parity can be measured by applying CNOT gates from each qubit that you want to measure (the control qubits) to an ancilla qubit ...


5

Well, I'm working on a simulator of a quantum computer currently. The basic idea of quantum computing, of course, is gates represented by matrices applied to qubits represented by vectors. Using Python's numpy package, this isn't that hard to program in the most basic sense. From there, one might expand upon, of course, the interface. One might also ...


5

You're getting the same output as Quirk, just with a different bit ordering convention for the kets. Quirk considers the top qubit to be the "least significant" qubit (i.e. if you count 000, 001, 010, ... then it refers to the rightmost bit). So if you apply a Hadamard gate to the top qubit of a three-qubit circuit in Quirk you get the state |000> + |001>. ...


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