@inproceedings{8159, abstract = {{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 = {{de Beaudrap, Niel and Gharibian, Sevag}}, booktitle = {{Proceedings of the 31st Conference on Computational Complexity (CCC 2016)}}, editor = {{Raz, Ran}}, isbn = {{978-3-95977-008-8}}, keywords = {{quantum 2-SAT, transfer matrix, strongly connected components, limited backtracking, local Hamiltonian}}, location = {{Tokyo, Japan}}, pages = {{27:1--17:21}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}}, title = {{{A Linear Time Algorithm for Quantum 2-SAT}}}, doi = {{10.4230/LIPIcs.CCC.2016.27}}, volume = {{50}}, year = {{2016}}, } @article{9745, abstract = {{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 = {{Fu, Bo and Li, Chao and Zhang, Jianming and Huang, Zhenwei and Hemsel, Tobias}}, issn = {{1948-5719}}, journal = {{Journal of Korean Physical Society}}, keywords = {{Piezoelectric langevin transducer, Transfer matrix method, Four (six)-pole element description, Pre-stressed bolt}}, number = {{4}}, pages = {{929}}, title = {{{Modeling of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods}}}, doi = {{10.3938/jkps.57.929}}, volume = {{57}}, year = {{2010}}, }