Loading…
Parity decision tree in classical–quantum separations for certain classes of Boolean functions
In this paper, we study the separation between the deterministic (classical) query complexity ( D ) and the exact quantum query complexity ( Q E ) of several Boolean function classes using the parity decision tree method. We first define the query friendly (QF) functions on n variables as the ones w...
Saved in:
| Published in: | Quantum information processing 2021-06, Vol.20 (6), Article 218 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| 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-c249t-6deca0221fd965b2a60ca6e6edba39efe3fd2e7bb9ecf0f9477331feab8642103 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c249t-6deca0221fd965b2a60ca6e6edba39efe3fd2e7bb9ecf0f9477331feab8642103 |
| container_end_page | |
| container_issue | 6 |
| container_start_page | |
| container_title | Quantum information processing |
| container_volume | 20 |
| creator | Mukherjee, Chandra Sekhar Maitra, Subhamoy |
| description | In this paper, we study the separation between the deterministic (classical) query complexity (
D
) and the exact quantum query complexity (
Q
E
) of several Boolean function classes using the parity decision tree method. We first define the query friendly (QF) functions on
n
variables as the ones with minimum deterministic query complexity
D
(
f
). We observe that for each
n
, there exists a non-separable class of QF functions such that
D
(
f
)
=
Q
E
(
f
)
. Further, we show that for some values of
n
, all the QF functions are non-separable. Then, we present QF functions for certain other values of
n
where separation can be demonstrated, in particular,
Q
E
(
f
)
=
D
(
f
)
-
1
. In a related effort, we also study the Maiorana–McFarland (MM)-type Bent functions. We show that while for any MM Bent function
f
on
n
variables
D
(
f
)
=
n
, separation can be achieved as
n
2
≤
Q
E
(
f
)
≤
⌈
3
n
4
⌉
. Our results highlight how different classes of Boolean functions can be analyzed for classical–quantum separation exploiting the parity decision tree method. |
| doi_str_mv | 10.1007/s11128-021-03158-1 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2545239658</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2545239658</sourcerecordid><originalsourceid>FETCH-LOGICAL-c249t-6deca0221fd965b2a60ca6e6edba39efe3fd2e7bb9ecf0f9477331feab8642103</originalsourceid><addsrcrecordid>eNp9kD1OxDAQRi0EEsvCBagsURs8duIkJaz4k5CggNo4zhhllY137aTYjjtwQ06C2YDoqGaK930zeoScAj8HzouLCACiZFwA4xLyksEemUFeSAZSiv3dzhkv8vyQHMW45IlUpZqR1ycT2mFLG7RtbH1Ph4BI257azsTYWtN9vn9sRtMP44pGXJtghoRF6nygFsNgflmM1Dt65X2Hpqdu7O0OPCYHznQRT37mnLzcXD8v7tjD4-394vKBWZFVA1PpAcOFANdUKq-FUdwahQqb2sgKHUrXCCzqukLruKuyopASHJq6VJkALufkbOpdB78ZMQ566cfQp5Na5FkuZKotEyUmygYfY0Cn16FdmbDVwPW3ST2Z1MmP3pnUkEJyCsUE928Y_qr_SX0Bjxd5vA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2545239658</pqid></control><display><type>article</type><title>Parity decision tree in classical–quantum separations for certain classes of Boolean functions</title><source>Springer Link</source><creator>Mukherjee, Chandra Sekhar ; Maitra, Subhamoy</creator><creatorcontrib>Mukherjee, Chandra Sekhar ; Maitra, Subhamoy</creatorcontrib><description>In this paper, we study the separation between the deterministic (classical) query complexity (
D
) and the exact quantum query complexity (
Q
E
) of several Boolean function classes using the parity decision tree method. We first define the query friendly (QF) functions on
n
variables as the ones with minimum deterministic query complexity
D
(
f
). We observe that for each
n
, there exists a non-separable class of QF functions such that
D
(
f
)
=
Q
E
(
f
)
. Further, we show that for some values of
n
, all the QF functions are non-separable. Then, we present QF functions for certain other values of
n
where separation can be demonstrated, in particular,
Q
E
(
f
)
=
D
(
f
)
-
1
. In a related effort, we also study the Maiorana–McFarland (MM)-type Bent functions. We show that while for any MM Bent function
f
on
n
variables
D
(
f
)
=
n
, separation can be achieved as
n
2
≤
Q
E
(
f
)
≤
⌈
3
n
4
⌉
. Our results highlight how different classes of Boolean functions can be analyzed for classical–quantum separation exploiting the parity decision tree method.</description><identifier>ISSN: 1570-0755</identifier><identifier>EISSN: 1573-1332</identifier><identifier>DOI: 10.1007/s11128-021-03158-1</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Boolean ; Boolean algebra ; Boolean functions ; Codes ; Complexity ; Data Structures and Information Theory ; Decision analysis ; Decision trees ; Mathematical analysis ; Mathematical Physics ; Parity ; Physics ; Physics and Astronomy ; Quantum Computing ; Quantum Information Technology ; Quantum Physics ; Queries ; Separation ; Spintronics</subject><ispartof>Quantum information processing, 2021-06, Vol.20 (6), Article 218</ispartof><rights>The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021</rights><rights>The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c249t-6deca0221fd965b2a60ca6e6edba39efe3fd2e7bb9ecf0f9477331feab8642103</citedby><cites>FETCH-LOGICAL-c249t-6deca0221fd965b2a60ca6e6edba39efe3fd2e7bb9ecf0f9477331feab8642103</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Mukherjee, Chandra Sekhar</creatorcontrib><creatorcontrib>Maitra, Subhamoy</creatorcontrib><title>Parity decision tree in classical–quantum separations for certain classes of Boolean functions</title><title>Quantum information processing</title><addtitle>Quantum Inf Process</addtitle><description>In this paper, we study the separation between the deterministic (classical) query complexity (
D
) and the exact quantum query complexity (
Q
E
) of several Boolean function classes using the parity decision tree method. We first define the query friendly (QF) functions on
n
variables as the ones with minimum deterministic query complexity
D
(
f
). We observe that for each
n
, there exists a non-separable class of QF functions such that
D
(
f
)
=
Q
E
(
f
)
. Further, we show that for some values of
n
, all the QF functions are non-separable. Then, we present QF functions for certain other values of
n
where separation can be demonstrated, in particular,
Q
E
(
f
)
=
D
(
f
)
-
1
. In a related effort, we also study the Maiorana–McFarland (MM)-type Bent functions. We show that while for any MM Bent function
f
on
n
variables
D
(
f
)
=
n
, separation can be achieved as
n
2
≤
Q
E
(
f
)
≤
⌈
3
n
4
⌉
. Our results highlight how different classes of Boolean functions can be analyzed for classical–quantum separation exploiting the parity decision tree method.</description><subject>Boolean</subject><subject>Boolean algebra</subject><subject>Boolean functions</subject><subject>Codes</subject><subject>Complexity</subject><subject>Data Structures and Information Theory</subject><subject>Decision analysis</subject><subject>Decision trees</subject><subject>Mathematical analysis</subject><subject>Mathematical Physics</subject><subject>Parity</subject><subject>Physics</subject><subject>Physics and Astronomy</subject><subject>Quantum Computing</subject><subject>Quantum Information Technology</subject><subject>Quantum Physics</subject><subject>Queries</subject><subject>Separation</subject><subject>Spintronics</subject><issn>1570-0755</issn><issn>1573-1332</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNp9kD1OxDAQRi0EEsvCBagsURs8duIkJaz4k5CggNo4zhhllY137aTYjjtwQ06C2YDoqGaK930zeoScAj8HzouLCACiZFwA4xLyksEemUFeSAZSiv3dzhkv8vyQHMW45IlUpZqR1ycT2mFLG7RtbH1Ph4BI257azsTYWtN9vn9sRtMP44pGXJtghoRF6nygFsNgflmM1Dt65X2Hpqdu7O0OPCYHznQRT37mnLzcXD8v7tjD4-394vKBWZFVA1PpAcOFANdUKq-FUdwahQqb2sgKHUrXCCzqukLruKuyopASHJq6VJkALufkbOpdB78ZMQ566cfQp5Na5FkuZKotEyUmygYfY0Cn16FdmbDVwPW3ST2Z1MmP3pnUkEJyCsUE928Y_qr_SX0Bjxd5vA</recordid><startdate>20210601</startdate><enddate>20210601</enddate><creator>Mukherjee, Chandra Sekhar</creator><creator>Maitra, Subhamoy</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20210601</creationdate><title>Parity decision tree in classical–quantum separations for certain classes of Boolean functions</title><author>Mukherjee, Chandra Sekhar ; Maitra, Subhamoy</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c249t-6deca0221fd965b2a60ca6e6edba39efe3fd2e7bb9ecf0f9477331feab8642103</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Boolean</topic><topic>Boolean algebra</topic><topic>Boolean functions</topic><topic>Codes</topic><topic>Complexity</topic><topic>Data Structures and Information Theory</topic><topic>Decision analysis</topic><topic>Decision trees</topic><topic>Mathematical analysis</topic><topic>Mathematical Physics</topic><topic>Parity</topic><topic>Physics</topic><topic>Physics and Astronomy</topic><topic>Quantum Computing</topic><topic>Quantum Information Technology</topic><topic>Quantum Physics</topic><topic>Queries</topic><topic>Separation</topic><topic>Spintronics</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mukherjee, Chandra Sekhar</creatorcontrib><creatorcontrib>Maitra, Subhamoy</creatorcontrib><collection>CrossRef</collection><jtitle>Quantum information processing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Mukherjee, Chandra Sekhar</au><au>Maitra, Subhamoy</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Parity decision tree in classical–quantum separations for certain classes of Boolean functions</atitle><jtitle>Quantum information processing</jtitle><stitle>Quantum Inf Process</stitle><date>2021-06-01</date><risdate>2021</risdate><volume>20</volume><issue>6</issue><artnum>218</artnum><issn>1570-0755</issn><eissn>1573-1332</eissn><abstract>In this paper, we study the separation between the deterministic (classical) query complexity (
D
) and the exact quantum query complexity (
Q
E
) of several Boolean function classes using the parity decision tree method. We first define the query friendly (QF) functions on
n
variables as the ones with minimum deterministic query complexity
D
(
f
). We observe that for each
n
, there exists a non-separable class of QF functions such that
D
(
f
)
=
Q
E
(
f
)
. Further, we show that for some values of
n
, all the QF functions are non-separable. Then, we present QF functions for certain other values of
n
where separation can be demonstrated, in particular,
Q
E
(
f
)
=
D
(
f
)
-
1
. In a related effort, we also study the Maiorana–McFarland (MM)-type Bent functions. We show that while for any MM Bent function
f
on
n
variables
D
(
f
)
=
n
, separation can be achieved as
n
2
≤
Q
E
(
f
)
≤
⌈
3
n
4
⌉
. Our results highlight how different classes of Boolean functions can be analyzed for classical–quantum separation exploiting the parity decision tree method.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s11128-021-03158-1</doi></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 1570-0755 |
| ispartof | Quantum information processing, 2021-06, Vol.20 (6), Article 218 |
| issn | 1570-0755 1573-1332 |
| language | eng |
| recordid | cdi_proquest_journals_2545239658 |
| source | Springer Link |
| subjects | Boolean Boolean algebra Boolean functions Codes Complexity Data Structures and Information Theory Decision analysis Decision trees Mathematical analysis Mathematical Physics Parity Physics Physics and Astronomy Quantum Computing Quantum Information Technology Quantum Physics Queries Separation Spintronics |
| title | Parity decision tree in classical–quantum separations for certain classes of Boolean functions |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-06T06%3A34%3A10IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Parity%20decision%20tree%20in%20classical%E2%80%93quantum%20separations%20for%20certain%20classes%20of%20Boolean%20functions&rft.jtitle=Quantum%20information%20processing&rft.au=Mukherjee,%20Chandra%20Sekhar&rft.date=2021-06-01&rft.volume=20&rft.issue=6&rft.artnum=218&rft.issn=1570-0755&rft.eissn=1573-1332&rft_id=info:doi/10.1007/s11128-021-03158-1&rft_dat=%3Cproquest_cross%3E2545239658%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c249t-6deca0221fd965b2a60ca6e6edba39efe3fd2e7bb9ecf0f9477331feab8642103%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2545239658&rft_id=info:pmid/&rfr_iscdi=true |