Comparative complexity of quantum and classical OBDDs for total and partial functions

We consider a model of computation for discrete functions—Ordered Binary Decision Diagrams (OBDD).We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of...

Full description

Saved in:
Bibliographic Details
Published in:Russian mathematics 2015-11, Vol.59 (11), p.26-35
Main Author: Gainutdinova, A. F.
Format: Article
Language:English
Subjects:
Mathematics
Mathematics and Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c288t-2e80b782db1156ca6d459df399f508670db2494eaf30cc017d842b1b770faf673
cites cdi_FETCH-LOGICAL-c288t-2e80b782db1156ca6d459df399f508670db2494eaf30cc017d842b1b770faf673
container_end_page 35
container_issue 11
container_start_page 26
container_title Russian mathematics
container_volume 59
creator Gainutdinova, A. F.
description We consider a model of computation for discrete functions—Ordered Binary Decision Diagrams (OBDD).We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of OBDD. It is known that for total functions bounded error quantum OBDDs can be exponentially more effective than deterministic and bounded error probabilistic OBDDs. We show that such quantum OBDDs also can be exponentially more effective than nondeterministic OBDDs (both quantum and classical). For partial functions the gap can be more significant. For partial function depending on a parameter k exact quantum OBDD has the width two. Deterministic and bounded error probabilistic OBDD for this function must have a width exponentially depending on k .
doi_str_mv 10.3103/S1066369X15110031
format article
fullrecord <record><control><sourceid>crossref_sprin</sourceid><recordid>TN_cdi_crossref_primary_10_3103_S1066369X15110031</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>10_3103_S1066369X15110031</sourcerecordid><originalsourceid>FETCH-LOGICAL-c288t-2e80b782db1156ca6d459df399f508670db2494eaf30cc017d842b1b770faf673</originalsourceid><addsrcrecordid>eNp9kMFOwzAQRC0EEqXwAdz8A4FdO3GcI7RQkCr1AJV6ixzHRqnSuNgOon-Pq3JD4rSzejuj1RByi3DHEfj9G4IQXFQbLBABOJ6RCVY8zyTC5jzphLMjvyRXIWwBCsFyMSHrmdvtlVex-zJUJ92b7y4eqLP0c1RDHHdUDS3VvQqh06qnq8f5PFDrPI0upv1IU0DskrbjoGPnhnBNLqzqg7n5nVOyfn56n71ky9XidfawzDSTMmbMSGhKydoGsRBaiTYvqtbyqrIFSFFC27C8yo2yHLQGLFuZswabsgSrrCj5lOApV3sXgje23vtup_yhRqiPvdR_ekkedvKEdDt8GF9v3eiH9OY_ph99yWWw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Comparative complexity of quantum and classical OBDDs for total and partial functions</title><source>Springer Nature</source><creator>Gainutdinova, A. F.</creator><creatorcontrib>Gainutdinova, A. F.</creatorcontrib><description>We consider a model of computation for discrete functions—Ordered Binary Decision Diagrams (OBDD).We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of OBDD. It is known that for total functions bounded error quantum OBDDs can be exponentially more effective than deterministic and bounded error probabilistic OBDDs. We show that such quantum OBDDs also can be exponentially more effective than nondeterministic OBDDs (both quantum and classical). For partial functions the gap can be more significant. For partial function depending on a parameter k exact quantum OBDD has the width two. Deterministic and bounded error probabilistic OBDD for this function must have a width exponentially depending on k .</description><identifier>ISSN: 1066-369X</identifier><identifier>EISSN: 1934-810X</identifier><identifier>DOI: 10.3103/S1066369X15110031</identifier><language>eng</language><publisher>New York: Allerton Press</publisher><subject>Mathematics ; Mathematics and Statistics</subject><ispartof>Russian mathematics, 2015-11, Vol.59 (11), p.26-35</ispartof><rights>Allerton Press, Inc. 2015</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c288t-2e80b782db1156ca6d459df399f508670db2494eaf30cc017d842b1b770faf673</citedby><cites>FETCH-LOGICAL-c288t-2e80b782db1156ca6d459df399f508670db2494eaf30cc017d842b1b770faf673</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27903,27904</link.rule.ids></links><search><creatorcontrib>Gainutdinova, A. F.</creatorcontrib><title>Comparative complexity of quantum and classical OBDDs for total and partial functions</title><title>Russian mathematics</title><addtitle>Russ Math</addtitle><description>We consider a model of computation for discrete functions—Ordered Binary Decision Diagrams (OBDD).We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of OBDD. It is known that for total functions bounded error quantum OBDDs can be exponentially more effective than deterministic and bounded error probabilistic OBDDs. We show that such quantum OBDDs also can be exponentially more effective than nondeterministic OBDDs (both quantum and classical). For partial functions the gap can be more significant. For partial function depending on a parameter k exact quantum OBDD has the width two. Deterministic and bounded error probabilistic OBDD for this function must have a width exponentially depending on k .</description><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><issn>1066-369X</issn><issn>1934-810X</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2015</creationdate><recordtype>article</recordtype><recordid>eNp9kMFOwzAQRC0EEqXwAdz8A4FdO3GcI7RQkCr1AJV6ixzHRqnSuNgOon-Pq3JD4rSzejuj1RByi3DHEfj9G4IQXFQbLBABOJ6RCVY8zyTC5jzphLMjvyRXIWwBCsFyMSHrmdvtlVex-zJUJ92b7y4eqLP0c1RDHHdUDS3VvQqh06qnq8f5PFDrPI0upv1IU0DskrbjoGPnhnBNLqzqg7n5nVOyfn56n71ky9XidfawzDSTMmbMSGhKydoGsRBaiTYvqtbyqrIFSFFC27C8yo2yHLQGLFuZswabsgSrrCj5lOApV3sXgje23vtup_yhRqiPvdR_ekkedvKEdDt8GF9v3eiH9OY_ph99yWWw</recordid><startdate>20151101</startdate><enddate>20151101</enddate><creator>Gainutdinova, A. F.</creator><general>Allerton Press</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20151101</creationdate><title>Comparative complexity of quantum and classical OBDDs for total and partial functions</title><author>Gainutdinova, A. F.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c288t-2e80b782db1156ca6d459df399f508670db2494eaf30cc017d842b1b770faf673</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2015</creationdate><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Gainutdinova, A. F.</creatorcontrib><collection>CrossRef</collection><jtitle>Russian mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Gainutdinova, A. F.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Comparative complexity of quantum and classical OBDDs for total and partial functions</atitle><jtitle>Russian mathematics</jtitle><stitle>Russ Math</stitle><date>2015-11-01</date><risdate>2015</risdate><volume>59</volume><issue>11</issue><spage>26</spage><epage>35</epage><pages>26-35</pages><issn>1066-369X</issn><eissn>1934-810X</eissn><abstract>We consider a model of computation for discrete functions—Ordered Binary Decision Diagrams (OBDD).We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of OBDD. It is known that for total functions bounded error quantum OBDDs can be exponentially more effective than deterministic and bounded error probabilistic OBDDs. We show that such quantum OBDDs also can be exponentially more effective than nondeterministic OBDDs (both quantum and classical). For partial functions the gap can be more significant. For partial function depending on a parameter k exact quantum OBDD has the width two. Deterministic and bounded error probabilistic OBDD for this function must have a width exponentially depending on k .</abstract><cop>New York</cop><pub>Allerton Press</pub><doi>10.3103/S1066369X15110031</doi><tpages>10</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1066-369X
ispartof Russian mathematics, 2015-11, Vol.59 (11), p.26-35
issn 1066-369X
1934-810X
language eng
recordid cdi_crossref_primary_10_3103_S1066369X15110031
source Springer Nature
subjects Mathematics
Mathematics and Statistics
title Comparative complexity of quantum and classical OBDDs for total and partial functions
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-24T09%3A42%3A31IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref_sprin&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Comparative%20complexity%20of%20quantum%20and%20classical%20OBDDs%20for%20total%20and%20partial%20functions&rft.jtitle=Russian%20mathematics&rft.au=Gainutdinova,%20A.%20F.&rft.date=2015-11-01&rft.volume=59&rft.issue=11&rft.spage=26&rft.epage=35&rft.pages=26-35&rft.issn=1066-369X&rft.eissn=1934-810X&rft_id=info:doi/10.3103/S1066369X15110031&rft_dat=%3Ccrossref_sprin%3E10_3103_S1066369X15110031%3C/crossref_sprin%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c288t-2e80b782db1156ca6d459df399f508670db2494eaf30cc017d842b1b770faf673%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true