3
$\begingroup$

1, If I understand correctly, people talk about BQP, QMA, etc are usually referring to digital quantum computer/Turing machine and not about analog quantum computer. Based on the papers http://arxiv.org/abs/1208.3334 and http://arxiv.org/abs/0712.0483 we know that almost all the quantum chemistry methods are QMA-complete/hard. However, like Hartree-Fock, DFT methods, etc still QMA-complete/hard on analog quantum computer? Are there any papers prove that digital and analog quantum computer are equal in computational complexity theory?

2, Assume there is a material/molecule, its Hamiltonian just exact the same as a Hartree-Fock/DFT equation, then we measure the ground state energy of this material/molecule, can we say this material/molecule act as an analog quantum computer and solve this QMA-complete/hard problem? If not, why?

$\endgroup$
  • $\begingroup$ 2. If one measured the ground state energy experimentally, it does not necessarily relates to the computational complexity. We don't know if nature is doing quantum computing herself.... $\endgroup$ – user26143 May 2 '14 at 14:22
  • $\begingroup$ @user26143 Now I see. I used to obfuscate experiment and analog computer concepts. Thank you. $\endgroup$ – user45703 May 2 '14 at 14:39
  • $\begingroup$ What do you mean by "analog quantum computer"? (This concept is not defined in the references provided.) Do you mean an "analog quantum simulator", i.e. a one-purpose quantum computer that simulates the dynamics of some hamiltonian and (in general) does not perform quantum error correction? It is mostly unknown from a theoretical point of view what analog quantum simulators can actually do. $\endgroup$ – Juan Bermejo Vega May 31 '14 at 15:25
  • 1
    $\begingroup$ @JuanBermejoVega yes, I just mean "analog quantum simulator" sorry for the inaccurate expression. Thank you for the information. $\endgroup$ – user45703 Jun 1 '14 at 4:05
2
$\begingroup$

Your second question is easy to answer: yes, you could say that. However, it is highly unlikely that you will find any experimental method to approximate the ground state energy of one of those QMA-hard models within a polynomial gap. If you did, you would find an efficient method to solve problems in QMA and therefore, problems in NP. We believe these problems cannot be solved efficiently within any realistic model of computation, classical or quantum.

Your first question is hard to answer in its current form. The classes BQP and QMA are well defined universally. A problem cannot and will not stop being QMA-hard just because you choose a specific model of quantum computer: you can ask, however, if your analog quantum simulator will be able to solve QMA-hard problems in polynomial time. This seems highly implausible, since QMA contains NP. Digital quantum computers should be able to simulate analog quantum computers and should just be more powerful than analogue ones (for instance, analog quantum simulators that implement dynamical evolutions can simulated digitally with the quantum algorithm of [Lloyd96]). Recall also that BQP is widely regarded as the class that most naturally captures the power of universal quantum computers.

An interesting question that you may ask is whether the complexity class BQP naturally capture the computational power of analog quantum simulators? (Recall that the definition of BQP is unique and you cannot change it, so it sounds more relevant to ask whether it is the natural class associated to the quantum model of computation that we consider.)

This answer to this question is currently unknown. However, the fact that analog quantum simulators are single-purpose highly specialized machines indicates that BQP might not be the complexity class that best captures their computational complexity: although their power should lie clearly within BQP, it is currently unclear whether they will be able to solve BQP-complete problems. It would be desirable to gain some insight into this question but there are some obstacles to tackle it with current techniques:

(1) there seems various different types of quantum simulator, so it is not clear to me whether one can define a computational model for all of them;

(2) many authors seem not to be interested in doing quantum error correction with their quantum simulators (and the scientific consensus to date is that quantum computers need quantum error correction to work and solve BQP-complete problems).

The case for error correction is crucial. If we can do error correction we know that we can do polynomially long quantum computations in the presence of noise due to the celebrated threshold theorem. However, if a quantum computation is not fault tolerant errors will accumulate and turn your (polynomially long) computation into garbage. Therefore, I think it is unnatural to assume that you can perform polynomially long quantum computations in a non fault tolerant way.

Yet, presently, many people often conceive analog quantum simulators as one-purpose quantum computers that does not do error correction. (Or, at least, in many talks, people seem not to be looking at that.) This definition is rather vague and it does not immediately define a computational model: to be rigorous we would need to specify what type of Hamiltonians we allow and what are our models of noise, dissipation, and, very importantly, what is the problem that the analog quantum simulator should solve. Regardless of these details, if analog quantum simulators do not implement quantum error correction, it seems unnatural to argue that BQP is the natural complexity class associated to this model. Yet, it seems natural to expect that these machines could perform some interesting quantum computations, such as e.g. constant-depth quantum computations (where the error propagation is mitigated). However, the computational complexity of constant-depth quantum circuits is not fully understood. There is some evidence suggesting that such circuits might have super-classical features.

Last, I should say clarify that many people are not trying to build analog quantum simulators just to have ``crappier quantum computers''. I think the motivation usually is to have testbed systems to study physical properties of complex many-body quantum systems. In many situations, people would just like to have a machine to some intuition on whether one had got the right Hamiltonian that describes a system, measure properties of phases and things like that. So, my point is, I do not think people are not proposing to use them as replacements of quantum computers. And, if that is not your goal, it is not that important whether they can solve all problems in BQP.

$\endgroup$
1
$\begingroup$

Most results from [quantum] complexity theory are for universal quantum computers. The circuit model has been proven to be universal, so has the adiabatic model (which is something like an analog that you're thinking of). Any quantum computing model that is universal is also equivalent to these other models (i.e. one can simulate the other with at most polynomial overhead), so the complexity class of an algorithm doesn't change when going from one to another. This is true for any models of computation that are equivalent (not just universal models).

$\endgroup$
  • $\begingroup$ So I can safely say that digital quantum computer and analog quantum computer are equal in the context of computational complexity theory(simulate each other with at most polynomial time), right? $\endgroup$ – user45703 May 2 '14 at 14:45
  • $\begingroup$ If you can prove their equivalence, then you are safe. $\endgroup$ – hadsed May 2 '14 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.