• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

205 submissions , 163 unreviewed
5,037 questions , 2,191 unanswered
5,345 answers , 22,706 comments
1,470 users with positive rep
816 active unimported users
More ...

  Are BQP, QMA concepts still right on analog quantum computer?

+ 2 like - 0 dislike

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?

This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user user45703
asked May 2, 2014 in Theoretical Physics by user45703 (10 points) [ no revision ]
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....

This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user user26143
@user26143 Now I see. I used to obfuscate experiment and analog computer concepts. Thank you.

This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user user45703
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.

This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user Juan Bermejo Vega
@JuanBermejoVega yes, I just mean "analog quantum simulator" sorry for the inaccurate expression. Thank you for the information.

This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user user45703

2 Answers

+ 1 like - 0 dislike

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

This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user hadsed
answered May 2, 2014 by hadsed (10 points) [ no revision ]
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?

This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user user45703
If you can prove their equivalence, then you are safe.

This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user hadsed
+ 0 like - 0 dislike

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 trickier. I would reformulate it as follows (let me know if you do not like my formulation): does the complexity class BQP naturally capture the computational power of analog quantum simulators? (Notice that the definition of BQP is unique and you cannot change it; the relevant question to me is whether it is the natural class associated to the quantum model of computation that we consider.)

So, I am going to try to answer my reformulation of your question. In short, I believe BQP might not be the relevant complexity class to talk about analog quantum simulators. I will focus on the class BQP because the question is already complicated for this class.

I believe it is presently unclear what type of computational problems analog quantum simulators can solve. In my view, this is hard to answer because of a combination of the following reasons: (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.

First of all, I would say that the honest answer is that we still do not know whether the complexity class BQP faithfully represents the computational power of analog quantum simulators. On the other hand, it is widely accepted that this class naturally captures the power of universal quantum computers, and this matters a lot.

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 do 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, etc. Regardless of these details, we should still regard any model of this kind as a non-fault tolerant model of quantum computation. Therefore, it seems hard to argue that BQP is the natural complexity class associated to this model. Yet, it seems natural to expect that these machines could perform at least constant-depth quantum computations, since they error propagation is mitigated so badly in low-depth computations. However, the computational complexity of constant-depth quantum circuits is not very well 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.

This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user Juan Bermejo Vega
answered Jun 4, 2014 by jbvega (285 points) [ no revision ]

Your answer

Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead.
To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL.
Please consult the FAQ for as to how to format your post.
This is the answer box; if you want to write a comment instead, please use the 'add comment' button.
Live preview (may slow down editor)   Preview
Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:
Then drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds).
Please complete the anti-spam verification

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights