---
_id: '8159'
abstract:
- lang: eng
  text: The Boolean constraint satisfaction problem 3-SAT is arguably the canonical
    NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial
    time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically
    motivated generalization of k-SAT to the quantum setting, defining the problem
    "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time
    on a classical computer, in particular in deterministic time O(n^4), assuming
    unit-cost arithmetic over a field extension of the rational numbers, where n is
    number of variables. In this paper, we present an algorithm for quantum 2-SAT
    which runs in linear time, i.e. deterministic time O(n+m) for n and m the number
    of variables and clauses, respectively. Our approach exploits the transfer matrix
    techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions
    for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT
    algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and
    Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].
author:
- first_name: Niel
  full_name: de Beaudrap, Niel
  last_name: de Beaudrap
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
citation:
  ama: 'de Beaudrap N, Gharibian S. A Linear Time Algorithm for Quantum 2-SAT. In:
    Raz R, ed. <i>Proceedings of the 31st Conference on Computational Complexity (CCC
    2016)</i>. Vol 50. Leibniz International Proceedings in Informatics (LIPIcs).
    Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2016:27:1-17:21. doi:<a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">10.4230/LIPIcs.CCC.2016.27</a>'
  apa: de Beaudrap, N., &#38; Gharibian, S. (2016). A Linear Time Algorithm for Quantum
    2-SAT. In R. Raz (Ed.), <i>Proceedings of the 31st Conference on Computational
    Complexity (CCC 2016)</i> (Vol. 50, p. 27:1-17:21). Schloss Dagstuhl - Leibniz-Zentrum
    fuer Informatik. <a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">https://doi.org/10.4230/LIPIcs.CCC.2016.27</a>
  bibtex: '@inproceedings{de Beaudrap_Gharibian_2016, place={Dagstuhl, Germany}, series={Leibniz
    International Proceedings in Informatics (LIPIcs)}, title={A Linear Time Algorithm
    for Quantum 2-SAT}, volume={50}, DOI={<a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">10.4230/LIPIcs.CCC.2016.27</a>},
    booktitle={Proceedings of the 31st Conference on Computational Complexity (CCC
    2016)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={de
    Beaudrap, Niel and Gharibian, Sevag}, editor={Raz, Ran}, year={2016}, pages={27:1–17:21},
    collection={Leibniz International Proceedings in Informatics (LIPIcs)} }'
  chicago: 'Beaudrap, Niel de, and Sevag Gharibian. “A Linear Time Algorithm for Quantum
    2-SAT.” In <i>Proceedings of the 31st Conference on Computational Complexity (CCC
    2016)</i>, edited by Ran Raz, 50:27:1-17:21. Leibniz International Proceedings
    in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
    fuer Informatik, 2016. <a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">https://doi.org/10.4230/LIPIcs.CCC.2016.27</a>.'
  ieee: 'N. de Beaudrap and S. Gharibian, “A Linear Time Algorithm for Quantum 2-SAT,”
    in <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>,
    Tokyo, Japan, 2016, vol. 50, p. 27:1–17:21, doi: <a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">10.4230/LIPIcs.CCC.2016.27</a>.'
  mla: de Beaudrap, Niel, and Sevag Gharibian. “A Linear Time Algorithm for Quantum
    2-SAT.” <i>Proceedings of the 31st Conference on Computational Complexity (CCC
    2016)</i>, edited by Ran Raz, vol. 50, Schloss Dagstuhl - Leibniz-Zentrum fuer
    Informatik, 2016, p. 27:1-17:21, doi:<a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">10.4230/LIPIcs.CCC.2016.27</a>.
  short: 'N. de Beaudrap, S. Gharibian, in: R. Raz (Ed.), Proceedings of the 31st
    Conference on Computational Complexity (CCC 2016), Schloss Dagstuhl - Leibniz-Zentrum
    fuer Informatik, Dagstuhl, Germany, 2016, p. 27:1–17:21.'
conference:
  location: Tokyo, Japan
  name: 31st Conference on Computational Complexity (CCC 2016)
date_created: 2019-03-01T11:19:54Z
date_updated: 2023-02-28T11:01:53Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.CCC.2016.27
editor:
- first_name: Ran
  full_name: Raz, Ran
  last_name: Raz
extern: '1'
external_id:
  arxiv:
  - '1508.07338'
intvolume: '        50'
keyword:
- quantum 2-SAT
- transfer matrix
- strongly connected components
- limited backtracking
- local Hamiltonian
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://drops.dagstuhl.de/opus/volltexte/2016/5836/
oa: '1'
page: 27:1-17:21
place: Dagstuhl, Germany
publication: Proceedings of the 31st Conference on Computational Complexity (CCC 2016)
publication_identifier:
  isbn:
  - 978-3-95977-008-8
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: A Linear Time Algorithm for Quantum 2-SAT
type: conference
user_id: '71541'
volume: 50
year: '2016'
...
---
_id: '9745'
abstract:
- lang: eng
  text: In the modeling of piezoelectric Langevin transducers using usual transfer
    matrix methods, some simplifications have been adopted. This leads to reduction
    of the model quality. A mixed transfer matrix method is employed in the modeling
    of Langevin transducers, where the pre-stressed bolt is modeled as a separate
    four-pole element, which is connected to other elements in parallel. Based on
    the mixed transfer matrix method, the four (six)-pole element description of the
    piezoelectric Langevin transducer is built up and the total transfer matrix relation
    is derived. The resonance frequencies of the transducer are calculated and then
    measured using the impedance analyzer (HP4192). Experimental result shows that
    the mixed transfer matrix method has better modeling quality than the usual transfer
    matrix method for the vibration analysis of piezoelectric Langevin transducers.
author:
- first_name: Bo
  full_name: Fu, Bo
  last_name: Fu
- first_name: Chao
  full_name: Li, Chao
  last_name: Li
- first_name: Jianming
  full_name: Zhang, Jianming
  last_name: Zhang
- first_name: Zhenwei
  full_name: Huang, Zhenwei
  last_name: Huang
- first_name: Tobias
  full_name: Hemsel, Tobias
  id: '210'
  last_name: Hemsel
citation:
  ama: Fu B, Li C, Zhang J, Huang Z, Hemsel T. Modeling of Piezoelectric Langevin
    Transducers by Using Mixed Transfer Matrix Methods. <i>Journal of Korean Physical
    Society</i>. 2010;57(4):929. doi:<a href="https://doi.org/10.3938/jkps.57.929">10.3938/jkps.57.929</a>
  apa: Fu, B., Li, C., Zhang, J., Huang, Z., &#38; Hemsel, T. (2010). Modeling of
    Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods. <i>Journal
    of Korean Physical Society</i>, <i>57</i>(4), 929. <a href="https://doi.org/10.3938/jkps.57.929">https://doi.org/10.3938/jkps.57.929</a>
  bibtex: '@article{Fu_Li_Zhang_Huang_Hemsel_2010, title={Modeling of Piezoelectric
    Langevin Transducers by Using Mixed Transfer Matrix Methods}, volume={57}, DOI={<a
    href="https://doi.org/10.3938/jkps.57.929">10.3938/jkps.57.929</a>}, number={4},
    journal={Journal of Korean Physical Society}, author={Fu, Bo and Li, Chao and
    Zhang, Jianming and Huang, Zhenwei and Hemsel, Tobias}, year={2010}, pages={929}
    }'
  chicago: 'Fu, Bo, Chao Li, Jianming Zhang, Zhenwei Huang, and Tobias Hemsel. “Modeling
    of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods.”
    <i>Journal of Korean Physical Society</i> 57, no. 4 (2010): 929. <a href="https://doi.org/10.3938/jkps.57.929">https://doi.org/10.3938/jkps.57.929</a>.'
  ieee: B. Fu, C. Li, J. Zhang, Z. Huang, and T. Hemsel, “Modeling of Piezoelectric
    Langevin Transducers by Using Mixed Transfer Matrix Methods,” <i>Journal of Korean
    Physical Society</i>, vol. 57, no. 4, p. 929, 2010.
  mla: Fu, Bo, et al. “Modeling of Piezoelectric Langevin Transducers by Using Mixed
    Transfer Matrix Methods.” <i>Journal of Korean Physical Society</i>, vol. 57,
    no. 4, 2010, p. 929, doi:<a href="https://doi.org/10.3938/jkps.57.929">10.3938/jkps.57.929</a>.
  short: B. Fu, C. Li, J. Zhang, Z. Huang, T. Hemsel, Journal of Korean Physical Society
    57 (2010) 929.
date_created: 2019-05-13T09:40:42Z
date_updated: 2022-01-06T07:04:19Z
department:
- _id: '151'
doi: 10.3938/jkps.57.929
intvolume: '        57'
issue: '4'
keyword:
- Piezoelectric langevin transducer
- Transfer matrix method
- Four (six)-pole element description
- Pre-stressed bolt
language:
- iso: eng
page: '929'
publication: Journal of Korean Physical Society
publication_identifier:
  issn:
  - 1948-5719
quality_controlled: '1'
status: public
title: Modeling of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix
  Methods
type: journal_article
user_id: '55222'
volume: 57
year: '2010'
...