{"id":275,"date":"2007-01-16T11:08:15","date_gmt":"2007-01-16T11:08:15","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/01\/16\/quantum-computation-complexity-bqp\/"},"modified":"2007-01-16T11:08:15","modified_gmt":"2007-01-16T11:08:15","slug":"quantum-computation-complexity-bqp","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/01\/16\/quantum-computation-complexity-bqp\/","title":{"rendered":"Quantum Computation Complexity: BQP"},"content":{"rendered":"

What started me on this whole complexity theory series was a question in
\nthe comments about the difference between quantum computers and classical
\ncomputers. Taking the broadest possible view, in theory, a quantum computer
\nis a kind of non-deterministic machine – so in the best possible case,
\na quantum machine can solve NP-complete problems in polynomial time. The set
\nof things computable on a quantum machine is not different from the set of
\nthings computable on a classical machine – but the things that are tractable<\/em> (solvable in a reasonable amount of time) on a quantum
\ncomputer may be different.<\/p>\n

<\/p>\n

The current proposed designs for quantum computers fall well short of being general non-deterministic machines – so the set of problems that are
\ntractable on a quantum automaton (QA) may not be as large as the set of problems tractable on a general non-deterministic automaton (NDA). <\/p>\n

To try to understand what we can do with a QA, there’s a complexity class
\nBQP – bounded probability quantum polynomial – to represent the things
\ncomputable in polynomial time using a quantum computer. BQP is basically the equivalent of P for conventional computers – it is part of the nature of the quantum machine that its programs are always<\/em> probabilistic.<\/p>\n

To really understand what BQP means, we need to take a moment to look at what a quantum computer is, in contrast to a conventional computer. The canonical example of a conventional computer for the purposes of computation theory is the turing machine. To make the contrast between the quantum automaton and the turing machine clearer, we’ll use a restricted definition of the Turing machine called a binary Turing machine. (The binary Turing machine is equivalent in power to the general Turing machine; in fact, some people use this restricted definition as the canonical definition of a TM.) <\/p>\n

A binary Turing machine consists of:<\/p>\n

    \n
  1. A tape<\/em>, which is an unbounded sequence of numbered cells,
    \neach of which may contain either a one or a zero.<\/li>\n
  2. A tape head<\/em>, which is positioned over some tape cell at any
    \npoint in time, and in any computation step, can read the value of a cell, write a new value into the cell, and move one step in either direction. <\/li>\n
  3. A state<\/em> consisting of a finite set of binary registers r1<\/sub>,…,rn<\/sub>.\n
  4. A state transition function<\/em> λ : (r1<\/sub>…rn<\/sub>) × (0|1) → (r’1<\/sub>…r’n<\/sub>) × (0|1) × (left|right), which takes the current state and the symbol under the tape head as input, and produces a new state, a symbol to be written to the tape cell, and a direction to move the head. <\/li>\n<\/ol>\n

    A computation starts with some input written onto the tape, with the tape head positioned at cell zero. Each step, it invokes the transition function,
    \nand updates the state, tape cell value, and head position based on the result. It continues to do this until it enters the state where all registers contain the value 0, at which point it halts. When the machine halts, the result<\/em> of the computation is the value on the tape.<\/p>\n

    A basic quantum machine is very similar – it also has a tape, a register
    \nset, and a transition function – but they’re all probabilistic. Instead of a
    \nquantum register\/tape cell containing a specific value of one or zero, it contains a probability function describing the quantum state of the register – effectively specifying the probability of seeing a one<\/em> when the value of the tape cell\/register is observed<\/em>; and instead of the transition function specifying a transition from a fixed state to a fixed state, it specifies how the probability function<\/em> for the registers\/tape cell varies.<\/p>\n

    The result is something similar<\/em> to BPP, but not quite the same. In BPP, you get to flip a coin to choose a path. But once you’ve chosen a path, you’re committed to that path. If that path turns out to be a dead end, there’s no way to get back the time you spent on the dead end. You’re committed to it, and you’ve already paid for it. In contrast, on a quantum machine, everything is happening in a sort of probability haze – until the end of the computation when you observe the result, it’s not committed to a single<\/em> path. It doesn’t have to set the value of a register to zero; it can effectively just change the probability function associated with that register; if a computation is a dead end, its contribution to the probability function will fade out<\/em> of the quantum state of the register.<\/p>\n

    But it’s not all good news for the quantum machine. Unfortunately, here’s where the direct correspondence between the quantum machine and the classical turing machine breaks down. In general, a quantum machine is effectively linear<\/em>. You don’t get to do something like a conditional in a quantum computation: at least for the technologies we’re looking at so far, they execute a linear<\/em> set of instructions. So you can’t branch. If you want to explore multiple paths, you need to encode the paths together in the probability functions. So effectively, the while the quantum transition function does get to alter the state and the tape cell, it does not<\/em> have a single fixed transition function: each transition function has a specific successor, and no matter what happens to the tape and the registers,
    \nthe transition function has to go through a specific sequence of values for the computation. So instead of a single transition function λ, the quantum machine has a sequence of functions {λ1<\/sub>,…,λn<\/sub>}, which must all be used in sequence during the computation. So, effectively, you can do small local
    \nbranches – that is, choices within the duration of a single transition function; but you can’t make choices the way you could with a non-quantum machine.<\/p>\n

    So what’s the difference between BPP and BQP? BQP allows the limited<\/em> exploration of multiple paths, instead of requiring an
    \na priori commitment to one of them.<\/p>\n

    In terms of the complexity hierarchy, P ⊆ BPP ⊆ BQP ⊆ PP. So BQP is at least<\/em> as powerful as BPP, and possibly better – but it’s bounded from above by PP. And in fact, PP is sufficiently different from BQP that being able to get the solution to a BQP problem in constant<\/em> time doesn’t grant any<\/em> additional capability to PP. (In fact, according to wikipedia, being able to solve BQP problems in zero<\/em> time doesn’t give any additional capability to PP; but I haven’t seen the proof of that.) So from what we know, BQP is very close to BPP; if P!=NP (as many of us expect), then BQP may be slighty larger that BPP, but no larger than PP.<\/p>\n","protected":false},"excerpt":{"rendered":"

    What started me on this whole complexity theory series was a question in the comments about the difference between quantum computers and classical computers. Taking the broadest possible view, in theory, a quantum computer is a kind of non-deterministic machine – so in the best possible case, a quantum machine can solve NP-complete problems in […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[80],"tags":[],"class_list":["post-275","post","type-post","status-publish","format-standard","hentry","category-computational-complexity"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-4r","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/275","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=275"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/275\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=275"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=275"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=275"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}