A very strange deadlock on key lock in SQL Server

Question

It is very strange that when there are 2 connections running the below transaction on different rows, deadlock is detected. Why the query optimizer require transaction T1 to have resource KEY2 which is the row updated by transaction T2?

KEY1 (ROW 1) KEY: 5:72057594048348160 (150fa2746afc)

KEY2 (ROW 2) KEY: 5:72057594048348160 (1bec117e39ae)

2 transactions are updating different rows at the same time. Suppose they are not interfering each other with UPLOCK and ROWLOCK?

BEGIN TRAN
SELECT * FROM TABLE WITH(UPLOCK, ROWLOCK) WHERE PK_COL1 = ? and PK_COL2 = ?
UPDATE TABLE SET COL3 = ? WHERE PK_COL1 = ? and PK_COL2 = ?
END

The following is the deadlock list

<process id="process10e7502c8" taskpriority="0" logused="0" waitresource="KEY: 5:72057594048348160 (150fa2746afc)" 
....
<process id="process10e750988" taskpriority="0" logused="0" waitresource="KEY: 5:72057594048348160 (1bec117e39ae)" 
...
<resource-list>
  <keylock hobtid="72057594048348160" dbid="5" objectname="" indexname="" id="locka6b73300" mode="U" associatedObjectId="72057594048348160">
    <owner-list>
      <owner id="process10e750988" mode="U" />
    </owner-list>
    <waiter-list>
      <waiter id="process10e7502c8" mode="U" requestType="wait" />
    </waiter-list>
  </keylock>
  <keylock hobtid="72057594048348160" dbid="5" objectname="" indexname="" id="locka5319b80" mode="U" associatedObjectId="72057594048348160">
    <owner-list>
      <owner id="process10e7502c8" mode="U" />
    </owner-list>
    <waiter-list>
      <waiter id="process10e750988" mode="U" requestType="wait" />
    </waiter-list>
  </keylock>
</resource-list>

Here is sp_lock result when deadlock occurred

spid    dbid    ObjId   IndId   Type    Resource    Mode    Status
51  5   0   0   DB                                      S   GRANT
52  6   0   0   DB                                      S   GRANT
53  4   0   0   DB                                      S   GRANT
54  5   0   0   DB                                      S   GRANT
54  5   1941581955  0   TAB                                     IX  GRANT
54  5   1941581955  1   KEY (1bec117e39ae)                      U   GRANT
54  5   0   0   MD  4(6:0:0)                            Sch-S   GRANT
54  5   1941581955  1   KEY (150fa2746afc)                      U   WAIT
54  5   1941581955  1   PAG 1:73626                             IU  GRANT
57  5   0   0   DB                                      S   GRANT
58  6   0   0   DB                                      S   GRANT
58  6   0   0   APP 16384:[Repl-LogRead]:(04dddec9)     X   GRANT
59  5   0   0   DB                                      S   GRANT
60  6   0   0   DB                                      S   GRANT
61  5   0   0   DB                                      S   GRANT
62  5   0   0   DB                                      S   GRANT
63  4   0   0   DB                                      S   GRANT
64  4   0   0   DB                                      S   GRANT
65  5   0   0   DB                                      S   GRANT
65  5   1941581955  1   KEY (1bec117e39ae)                      U   WAIT
65  5   1941581955  1   PAG 1:73626                             IU  GRANT
65  5   0   0   MD  4(6:0:0)                            Sch-S   GRANT
65  5   1941581955  1   KEY (150fa2746afc)                      U   GRANT
65  5   1941581955  0   TAB                                     IX  GRANT
66  6   0   0   APP 16384:[DC1ISGSD03\I]:(152e28ac)     X   GRANT
66  6   0   0   DB                                      S   GRANT
67  1   1131151075  0   TAB                                     IS  GRANT
69  5   0   0   DB                                      S   GRANT

If I add an unclustered index with the same columns and ordering as clustered index created by primary key, the deadlock problem disappears. But why update a row on a clustered index key required update lock on other clustered index key?

Please correct me if I have any misunderstanding. Any answers will be appreciated.

The table schema is described as below SQL script

create table [dbo].[TABLE1]
(
[PK_COL1] char(10) not null,
[PK_COL2] char(10) not null,
[COL3] char(10) not null,
PRIMARY KEY ([PK_COL1],[PK_COL2])
);

Answer 1

Add the READPAST hint:

BEGIN TRAN
    SELECT * FROM TABLE WITH(UPDLOCK, ROWLOCK, READPAST) 
    WHERE PK_COL1 = ? and PK_COL2 = ?
    UPDATE TABLE SET COL3 = ? WHERE PK_COL1 = ? and PK_COL2 = ?
COMMIT TRAN

As @CJBS noted in comments use of hints should be limited to situations where they are required and you fully understand the consequences.

The hints in the example above occur in example of using a table as a queue, where you want to select a single row, hold a lock on it, update in a separate statement (such as deleting the row once processed), but also to allow other readers to read rows past the held update lock.

Answer 2

I finally found out that non-clustered index is needed to avoid deadlock.

CREATE NONCLUSTERED INDEX [TABLE1_IDX1] ON [TABLE1]([PK_COL1], [PK_COL2]);